Search

Low-rank matrix approximation is a fundamental tool in data analysis for processing large datasets, reducing noise, and finding important signals. In this work, we present a novel truncated LU factorization called Spectrum-Revealing LU (SRLU) for effective low-rank matrix approximation, and develop a fast algorithm to compute an SRLU factorization. We provide both matrix and singular value approximation error bounds for the SRLU approximation computed by our algorithm. Our analysis suggests that SRLU is competitive with the best low-rank matrix approximation methods, deterministic or randomized, in both computational complexity and approximation quality. Numeric experiments illustrate that SRLU preserves sparsity, highlights important data features and variables, can be efficiently updated, and calculates data approximations nearly as accurately as possible. To the best of our knowledge this is the first practical variant of the LU factorization for effective and efficient low-rank matrix approximation.

Gaussian elimination with partial pivoting (GEPP) has long been among the most widely used methods for computing the LU factorization of a given matrix. However, this method is also known to fail for matrices that induce large element growth during the factorization process. In this paper, we propose a new scheme, Gaussian elimination with randomized complete pivoting (GERCP) for the efficient and reliable LU factorization of a given matrix. GERCP satisfies GECP (Gaussian elimination with complete pivoting) style element growth bounds with high probability, yet costs only marginally higher than GEPP. Our numerical experimental results strongly suggest that GERCP is as reliable as GECP and as efficient as GEPP for computing the LU factorization., Comment: 5 figures, 33 pages

The dominant contribution to communication complexity in factorizing a matrix using QR with column pivoting is due to column-norm updates that are required to process pivot decisions. We use randomized sampling to approximate this process which dramatically reduces communication in column selection. We also introduce a sample update formula to reduce the cost of sampling trailing matrices. Using our column selection mechanism we observe results that are comparable in quality to those obtained from the QRCP algorithm, but with performance near unpivoted QR. We also demonstrate strong parallel scalability on shared memory multiple core systems using an implementation in Fortran with OpenMP. This work immediately extends to produce low-rank truncated approximations of large matrices. We propose a truncated QR factorization with column pivoting that avoids trailing matrix updates which are used in current implementations of level-3 BLAS QR and QRCP. Provided the truncation rank is small, avoiding trailing matrix updates reduces approximation time by nearly half. By using these techniques and employing a variation on Stewart's QLP algorithm, we develop an approximate truncated SVD that runs nearly as fast as truncated QR.

Spectral graph sparsification has emerged as a powerful tool in the analysis of large-scale networks by reducing the overall number of edges, while maintaining a comparable graph Laplacian matrix. In this paper, we present an efficient algorithm for the construction of a new type of spectral sparsifier, the unweighted spectral sparsifier. Given a general undirected and unweighted graph $G = (V, E)$ and an integer $\ell < |E|$ (the number of edges in $E$), we compute an unweighted graph $H = (V, F)$ with $F \subset E$ and $|F| = \ell$ such that for every $x \in \mathbb{R}^{V}$ \[ {\displaystyle \frac{x^T L_G x}{\kappa} \leq x^T L_H x \leq x^T L_G x,} \] where $L_G$ and $L_H$ are the Laplacian matrices for $G$ and $H$, respectively, and $\kappa \geq 1$ is a slowly-varying function of $|V|, |E|$ and $\ell$. This work addresses the open question of the existence of unweighted graph sparsifiers for unweighted graphs. Additionally, our algorithm can efficiently compute unweighted graph sparsifiers for weighted graphs, leading to sparsified graphs that retain the weights of the original graphs.

A classical problem in matrix computations is the efficient and reliable approximation of a given matrix by a matrix of lower rank. The truncated singular value decomposition (SVD) is known to provide the best such approximation for any given fixed rank. However, the SVD is also known to be very costly to compute. Among the different approaches in the literature for computing low-rank approximations, randomized algorithms have attracted researchers' recent attention due to their surprising reliability and computational efficiency in different application areas. Typically, such algorithms are shown to compute with very high probability low-rank approximations that are within a constant factor from optimal, and are known to perform even better in many practical situations. In this paper, we present a novel error analysis that considers randomized algorithms within the subspace iteration framework and show with very high probability that highly accurate low-rank approximations as well as singular values can indeed be computed quickly for matrices with rapidly decaying singular values. Such matrices appear frequently in diverse application areas such as data analysis, fast structured matrix computations and fast direct methods for large sparse linear systems of equations and are the driving motivation for randomized methods. Furthermore, we show that the low-rank approximations computed by these randomized algorithms are actually rank-revealing approximations, and the special case of a rank-1 approximation can also be used to correctly estimate matrix 2-norms with very high probability. Our numerical experiments are in full support of our conclusions., Comment: 45 pages, 5 figures

A novel plasmonic waveguide-coupled nanocavity with a monopole antenna is proposed to localize the optical power from a hybrid plasmonic waveguide and subsequently convert it into electrical current. The nanocavity is designed as a Fabry-P\'erot waveguide resonator, while the monopole antenna is made of a metallic nanorod directly mounted onto the metallic part of the waveguide terminal which acts as the conducting ground. The nanocavity coincides with the antenna feed sandwiched in between the antenna and the ground. Maximum power from the waveguide can be coupled into, and absorbed in the nanocavity by means of the field resonance in the antenna as well as in the nanocavity. Simulation results show that 42% optical power from the waveguide can be absorbed in a germanium filled nanocavity with a nanoscale volume of 220x150x60nm$^3$. The design may find applications in nanoscale photo-detection, subwavelength light focusing and manipulating, as well as sensing., Comment: 10 pages, 5 figures

A plasmonic coupled-cavity system, which consists of a quarter-wave coupler cavity, a resonant Fabry-Perot detector nanocavity, and an off-resonant reflector cavity, is used to enhance the localization of surface plasmons in a plasmonic detector. The coupler cavity is designed based on transmission line theory and wavelength scaling rules in the optical regime, while the reflector cavity is derived from off-resonant resonator structures to attenuate transmission of plasmonic waves. We observed strong coupling of the cavities in simulation results, with an 86% improvement of surface plasmon localization achieved. The plasmonic coupled-cavity system may find useful applications in areas of nanoscale photodetectors, sensors, and an assortment of plasmonic-circuit devices., Comment: 9 pages, 5 figures

Traditionally, Bluetooth has been deemed unsuitable for sustaining a large-scale multi-hop network. There are two main reasons: severe frequency channel collisions under a large-scale network and high complexity of designing an efficient formation protocol. In this work, we reconsider this viewpoint from a practical usability perspective and aim to realize the buried potential of Bluetooth. Firstly, we find that the collision probability under a low-overhead network is fairly small, which is acceptable for practical applications. Secondly, we propose BlueSky, a complete system solution to provide necessary networking functionalities for Bluetooth. In BlueSky, we develop a connection maintenance mechanism for mitigating the influence of collisions and a network formation protocol for reliable packet transmissions. We implement BlueSky on Windows Mobile using 100 commercial smartphones. Comprehensive usability evaluations demonstrate the negligible overheads of BlueSky and its good network performance. In particular, 90%-95% of the whole 100 nodes can participate in the communication smoothly., Comment: We need to improve this paper further