Low-rank approximation with 1/𝜖 1/3 matrix-vector products

DOI10.1145/3519935.3519988MaRDI QIDQ6083565zbMATH OpenFDO

Authors Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.05120

zbMATH Keywords

Krylov methodslow-rank approximationmatrix-vector product modelSchatten norms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Here, given access to a matrix $A$ through matrix-vector products, an accuracy parameter $epsilon$, and a target rank $k$, the goal is to find a rank-$k$ matrix $Z$ with orthonormal columns such that $|A(I-Z{Z}^{o}p){|}_{S_p}leq(1+epsilon)mi{n}_{U^{o}pU=I_k}|A(I-U{U}^{o}p){|}_{S_p}$, where $|M{|}_{S_p}$ denotes the $el{l}_p$ norm of the the singular values of $M$. For the special cases of $p=2$ (Frobenius norm) and $p=infty$ (Spectral norm), Musco and Musco (NeurIPS 2015) obtained an algorithm based on Krylov methods that uses $ildeO(k/sqrtepsilon)$ matrix-vector products, improving on the na"ive $ildeO(k/epsilon)$ dependence obtainable by the power method, where $ildeO$ suppresses poly$(log(dk/epsilon))$ factors. Our main result is an algorithm that uses only $ildeO(k{p}^{1/6}/epsilo{n}^{1/3})$ matrix-vector products, and works for all $pgeq1$. For $p=2$ our bound improves the previous $ildeO(k/epsilo{n}^{1/2})$ bound to $ildeO(k/epsilo{n}^{1/3})$. Since the Schatten-$p$ and Schatten-$infty$ norms are the same up to a $(1+epsilon)$-factor when $pgeq(logd)/epsilon$, our bound recovers the result of Musco and Musco for $p=infty$. Further, we prove a matrix-vector query lower bound of $Omega(1/epsilo{n}^{1/3})$ for any fixed constant $pgeq1$, showing that surprisingly $ildeTheta(1/epsilo{n}^{1/3})$ is the optimal complexity for constant~$k$. To obtain our results, we introduce several new techniques, including optimizing over multiple Krylov subspaces simultaneously, and pinching inequalities for partitioned operators. Our lower bound for $pin[1,2]$ uses the Araki-Lieb-Thirring trace inequality, whereas for $p>2$, we appeal to a norm-compression inequality for aligned partitioned operators.

Recommendations

• Low-rank approximation of a matrix: novel insights, new progress, and extensions
• A cross-product approach for low-rank approximations of large matrices
• Low-rank approximation of tensors
• Lower bounds for the low-rank matrix approximation
• Low rank approximation with entrywise \(\ell_1\)-norm error
• Generalized low rank approximations of matrices
• Generalized low rank approximations of matrices
• Fast low rank approximations of matrices and tensors
• A low-rank approximation for computing the matrix exponential norm
• Low-rank matrix approximation in the infinity norm

Cited in

(8)

• A three-way Jordan canonical form as limit of low-rank tensor approximations
• Comparison of matrix norm sparsification
• Query lower bounds for log-concave sampling
• Algorithm-agnostic low-rank approximation of operator monotone matrix functions
• Fixed-sparsity matrix approximation from matrix-vector products
• Quasi-optimal hierarchically semi-separable matrix approximation
• A recursive butterfly factorization with optimality guarantees
• Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators I. Separable approximation of multi-variate functions

This page was built for publication: Low-rank approximation with 1/𝜖 ^1/3 matrix-vector products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083565)