Pith. sign in

REVIEW 2 cited by

Close to optimal column approximations with a single SVD

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2308.09068 v2 pith:GRO7U7MB submitted 2023-08-17 math.NA cs.NA

Alexander Osinsky This is my paper · ORCID
classification math.NAcs.NA
keywords columnapproximationbounddecompositionsamesinglesingularsubmatrix
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

The best column approximation in the Frobenius norm with $r$ columns has an error at most $\sqrt{r+1}$ times larger than the truncated singular value decomposition. Reaching this bound in practice involves either expensive random volume sampling or at least $r$ executions of singular value decomposition. In this paper it will be shown that the same column approximation bound can be reached with only a single SVD (which can also be replaced with approximate SVD). As a corollary, it will be shown how to find a highly nondegenerate submatrix in $r$ rows of size $N$ in just $O(Nr^2)$ operations, which mostly has the same properties as the maximum volume submatrix.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Compression Properties for large Toeplitz-like matrices

    math.NA 2025-02 conditional novelty 7.0 of 10

    For Toeplitz-like matrices, the paper proves explicit epsilon-rank bounds of order rho log(m) log(1/epsilon) for off-diagonal submatrices of the transformed matrix and uses them to build adaptive HODLR and HSS compres...

  2. Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation

    math.NA 2024-12 accept novelty 6.0 of 10

    Adaptive Randomized Pivoting is a cheap adaptive leverage-score sampler that matches the optimal expected Frobenius error for column subset selection and yields new expected-error bounds for DEIM, cross, and Nyström a...

Pith tools