More Like this

1. Faster Kernel Matrix Algebra via Density Estimation

   Backurs, A; Indyk, P; Musco, C; Wagner, T (January 2021, International Conference on Machine Learning)

   null (Ed.)

   We study fast algorithms for computing basic properties of an n x n positive semidefinite kernel matrix K corresponding to n points x_1,...,x_n in R^d. In particular, we consider the estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. These are some of the most basic problems defined over kernel matrices. We show that the sum of matrix entries can be estimated up to a multiplicative factor of 1+epsilon in time sublinear in n and linear in d for many popular kernel functions, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and a witnessing approximate eigenvector) can be approximated to a multiplicative factor of 1+epsilon in time sub-quadratic in n and linear in d. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation. 

   more » « less
2. Ensemble-based estimates of eigenvector error for empirical covariance matrices

   https://doi.org/10.1093/imaiai/iay010  

   Taylor, Dane; Restrepo, Juan G; Meyer, François G (July 2018, Information and Inference: A Journal of the IMA)

   Abstract Covariance matrices are fundamental to the analysis and forecast of economic, physical and biological systems. Although the eigenvalues $$\{\lambda _i\}$$ and eigenvectors $$\{\boldsymbol{u}_i\}$$ of a covariance matrix are central to such endeavours, in practice one must inevitably approximate the covariance matrix based on data with finite sample size $$n$$ to obtain empirical eigenvalues $$\{\tilde{\lambda }_i\}$$ and eigenvectors $$\{\tilde{\boldsymbol{u}}_i\}$$, and therefore understanding the error so introduced is of central importance. We analyse eigenvector error $$\|\boldsymbol{u}_i - \tilde{\boldsymbol{u}}_i \|^2$$ while leveraging the assumption that the true covariance matrix having size $$p$$ is drawn from a matrix ensemble with known spectral properties—particularly, we assume the distribution of population eigenvalues weakly converges as $$p\to \infty $$ to a spectral density $$\rho (\lambda )$$ and that the spacing between population eigenvalues is similar to that for the Gaussian orthogonal ensemble. Our approach complements previous analyses of eigenvector error that require the full set of eigenvalues to be known, which can be computationally infeasible when $$p$$ is large. To provide a scalable approach for uncertainty quantification of eigenvector error, we consider a fixed eigenvalue $$\lambda $$ and approximate the distribution of the expected square error $$r= \mathbb{E}\left [\| \boldsymbol{u}_i - \tilde{\boldsymbol{u}}_i \|^2\right ]$$ across the matrix ensemble for all $$\boldsymbol{u}_i$$ associated with $$\lambda _i=\lambda $$. We find, for example, that for sufficiently large matrix size $$p$$ and sample size $n> p$, the probability density of $$r$$ scales as $1/nr^2$. This power-law scaling implies that the eigenvector error is extremely heterogeneous—even if $$r$$ is very small for most eigenvectors, it can be large for others with non-negligible probability. We support this and further results with numerical experiments. 

   more » « less
3. A Fast and Effective Memristor-Based Method for Finding Approximate Eigenvalues and Eigenvectors of Non-negative Matrices

   https://doi.org/10.1109/ISVLSI.2018.00108  

   Wang, Chenghong; Jalali, Zeinab S.; Ding, Caiwen; Wang, Yanzhi; Soundarajan, Sucheta (July 2018, 2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI))

   Throughout many scientific and engineering fields, including control theory, quantum mechanics, advanced dynamics, and network theory, a great many important applications rely on the spectral decomposition of matrices. Traditional methods such as the power iteration method, Jacobi eigenvalue method, and QR decomposition are commonly used to compute the eigenvalues and eigenvectors of a square and symmetric matrix. However, these methods suffer from certain drawbacks: in particular, the power iteration method can only find the leading eigen-pair (i.e., the largest eigenvalue and its corresponding eigenvector), while the Jacobi and QR decomposition methods face significant performance limitations when facing with large scale matrices. Typically, even producing approximate eigenpairs of a general square matrix requires at least O(N^3) time complexity, where N is the number of rows of the matrix. In this work, we exploit the newly developed memristor technology to propose a low-complexity, scalable memristor-based method for deriving a set of dominant eigenvalues and eigenvectors for real symmetric non-negative matrices. The time complexity for our proposed algorithm is O(N^2 /Δ) (where Δ governs the accuracy). We present experimental studies to simulate the memristor-supporting algorithm, with results demonstrating that the average error for our method is within 4%, while its performance is up to 1.78X better than traditional methods. 

   more » « less
4. Sublinear Time Approximation of Text Similarity Matrices

   Ray, Archan; Monath, Nicholas; McCallum, Andrew; Musco, Cameron (February 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study algorithms for approximating pairwise similarity matrices that arise in natural language processing. Generally, computing a similarity matrix for $$n$$ data points requires $$\Omega(n^2)$$ similarity computations. This quadratic scaling is a significant bottleneck, especially when similarities are computed via expensive functions, e.g., via transformer models. Approximation methods reduce this quadratic complexity, often by using a small subset of exactly computed similarities to approximate the remainder of the complete pairwise similarity matrix. Significant work focuses on the efficient approximation of positive semidefinite (PSD) similarity matrices, which arise e.g., in kernel methods. However, much less is understood about indefinite (non-PSD) similarity matrices, which often arise in NLP. Motivated by the observation that many of these matrices are still somewhat close to PSD, we introduce a generalization of the popular \emph{Nystrom method} to the indefinite setting. Our algorithm can be applied to any similarity matrix and runs in sublinear time in the size of the matrix, producing a rank-$$s$$ approximation with just $O(ns)$ similarity computations. We show that our method, along with a simple variant of CUR decomposition, performs very well in approximating a variety of similarity matrices arising in NLP tasks. We demonstrate high accuracy of the approximated similarity matrices in tasks of document classification, sentence similarity, and cross-document coreference. 

   more » « less
5. Progress on Meson-Baryon Scattering

   https://doi.org/10.22323/1.396.0170  

   C. Morningstar; J. Bulava; A. Hanlon; B. Hörz; D. Mohler; A. Nicholson; S. Skinner; A. Walker-Loud (January 2021, 38th International Symposium on Lattice Field Theory, LATTICE2021 26th-30th July, 2021)

   Progress in computing various meson-baryon scattering amplitudes is presented on a single en- semble from the Coordinated Lattice Simulations (CLS) consortium with m π = 200 MeV and Nf = 2 + 1 dynamical fermions. The finite-volume Lüscher approach is employed to determine the lowest few partial waves from ground- and excited-state energies computed from correla- tion matrices rotated in a single pivot using a generalized eigenvector solution. This analysis requires evaluating matrices of correlation functions between single- and two-hadron interpolat- ing operators which are projected onto definite spatial momenta and finite-volume irreducible representations. The stochastic LapH method is used to estimate all needed quark propagators. Preliminary results are presented for I = 1/2, 3/2 N π amplitudes including the ∆(1232) resonance and the I = 0 S-wave amplitude with unit strangeness relevant for the Λ(1405). 

   more » « less