Lune

FOCS2020Top-tier venue

Robust and Sample Optimal Algorithms for PSD Low Rank Approximation

Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff

Abstract

Recently, Musco and Woodruff (FOCS, 2017) showed that given an n×n positive semidefinite (PSD) matrix A, it is possible to compute a (1+ε-approximate relative-error low-rank approximation to A by querying Õ(nk/ε2.5) entries of A in time Õ(nk/ε2.5+nkω-1/ε2(ω-1)). They also showed that any relative-error low-rank approximation algorithm must query Ω(nk/ε) entries of A, this gap has since remained open. Our main result is to resolve this question by obtaining an optimal algorithm that queries Õ(nk/ε) entries of A and outputs a relative-error low-rank approximation in Õ(n·(k/ε)ω-1) time. Note, our running time improves that of Musco and Woodruff, and matches the information-theoretic lower bound if the matrix-multiplication exponent ω is 2. We then extend our techniques to negative-type distance matrices. Here, our input is a pair-wise distance matrix A corresponding to a point set P=x1, x2, ..., xn such that Ai,j=||xi-xj||22. Bakshi and Woodruff (NeurIPS, 2018) showed a bi-criteria, relative-error low-rank approximation for negative-type metrics. Their algorithm queries Õ(nk/ε2.5) entries and outputs a rank-( k+4) matrix. We show that the bi-criteria guarantee is not necessary and obtain an Õ(nk/ε) query algorithm, which is optimal. Our algorithm applies to all distance matrices that arise from metrics satisfying negative-type inequalities, including l1,l2, spherical metrics, hypermetrics and effective resistances on a graph. We also obtain faster algorithms for ridge regression. Next, we introduce a new robust low-rank approximation model which captures PSD matrices that have been corrupted with noise. We assume that the Frobenius norm of the corruption is bounded. Here, we relax the notion of approximation to additive-error, since it is information-theoretically impossible to obtain a relative-error approximation in this setting. While a sample complexity lower bound precludes sublinear algorithms for arbitrary PSD matrices, we provide the first sublinear time and query algorithms when the corruption on the diagonal entries is bounded. As a special case, we show sample-optimal sublinear time algorithms for low-rank approximation of correlation matrices corrupted by noise.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

14 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Krylov Methods are (nearly) Optimal for Low-Rank Approximation cites Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
  • Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra cites Testing Positive Semi-Definiteness via Random Submatrices
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers14

  1. Quantum-Inspired Algorithms from Randomized Numerical Linear AlgebraNadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin et al.ICML 2022 · 25 citations
  2. Krylov Methods are (nearly) Optimal for Low-Rank ApproximationAinesh Bakshi, Shyam NarayananFOCS 2023 · 14 citations
  3. In-Database Regression in Input Sparsity TimeRajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng YeICML 2021 · 8 citations
  4. Testing Positive Semi-Definiteness via Random SubmatricesAinesh Bakshi, Nadiia Chepurko, Rajesh JayaramFOCS 2020 · 8 citations
  5. Faster Linear Algebra for Distance MatricesPiotr Indyk, Sandeep SilwalNeurIPS 2022 · 6 citations

Related papers

  1. Sublinear Time Low-Rank Approximation of Toeplitz MatricesCameron Musco, Kshiteej ShethSODA 2024 · 1 citation
  2. Input-Sparsity Low Rank Approximation in Schatten NormYi Li, David P. WoodruffICML 2020 · 14 citations
  3. Toeplitz Low-Rank Approximation with Sublinear Query ComplexityMichael Kapralov, Hannah Lawrence, Mikhail Makarov, Cameron Musco et al.SODA 2023 · 1 citation
  4. New Subset Selection Algorithms for Low Rank Approximation: Offline and OnlineDavid P. Woodruff, Taisuke YasudaSTOC 2023 · 3 citations
  5. Optimal ℓ1 Column Subset Selection and a Fast PTAS for Low Rank ApproximationArvind V. Mahankali, David P. WoodruffSODA 2021 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines