Pith. sign in

REVIEW 1 major objections 4 minor 46 references

Perturbations of CUR Decompositions

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Noisy CUR decompositions have error controlled by a single index-set constant in every Schatten p-norm.

desk verdict A solid, genuinely useful perturbation analysis for CUR decompositions, with honest bounds across all Schatten p-norms; the main caveat is that every theorem hinges on the clean submatrices having full rank, which the paper states but does not help the reader ensure. read the letter →

arxiv 1908.08101 v2 pith:NQXQTL4Y submitted 2019-08-21 math.NA cs.NA

Keaton Hamm , Longxiu Huang This is my paper · ORCID
classification math.NAcs.NA MSC 15A2365F3068P9968W20
keywords CURdecompositionlow-rankmatrixapproximationperturbationtheorySchattenp-normMoore-Penrosepseudoinversemaximal-volumesubmatrixrankenforcementunitarilyinvariantnorm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks what happens to a CUR decomposition when the low-rank matrix $A=W_k\Sigma_k V_k^*$ is observed as $A+E$. It claims that every standard variant of the CUR approximation has error bounded by a small multiple of the noise norm $\|E\|$, with the multiplier built from the norms of the pseudoinverses of the selected submatrices of the singular-vector matrices $W_k$ and $V_k$. Since the bounds are stated for every normalized, uniformly generated, unitarily invariant norm, they cover the spectral, Frobenius, and nuclear norms in one statement. The practical upshot is that the analysis separates the effect of noise from the effect of row and column choice, and it improves known constants when maximal-volume submatrices are selected.

What carries the argument

The argument rests on the exact CUR identities $A=CU^\dagger R$ and $A=CC^\dagger AR^\dagger R$ (Theorem 2.2), which hold when the selected submatrices have rank $k$. Proposition 6.4 identifies the norms $\|CU^\dagger\|$ and $\|U^\dagger R\|$ with $\|W_{k,I}^\dagger\|$ and $\|V_{k,J}^\dagger\|$, converting every perturbation deviation into quantities involving only the selected singular-vector rows. The perturbation theorems for pseudoinverses and singular values (Theorems 7.1 and 7.2) then supply the linear-in-noise skeleton, while the maximal-volume estimates place explicit bounds on the pseudoinverse constants.

What would settle it

A direct numerical test would settle it: fix a low-rank $A$ and index sets $I,J$ satisfying the full-rank assumption, then compute the maximum over noise matrices with $\|E\|=1$ of $\|A-\tilde C\tilde C^\dagger\tilde A\tilde R^\dagger\tilde R\|/\|E\|$ and compare it with $\|W_{k,I}^\dagger\|+\|V_{k,J}^\dagger\|+3$. Any ratio above the bound refutes Theorem 4.1. In the rank-one case $A=\mathrm{diag}(1,0)$ with $I=J=\{1\}$, this ratio can be computed in closed form from the four entries of $E$.

Watch

Extended reading notes

Core claim

The central claim is that for an exactly low-rank matrix $A=W_k\Sigma_k V_k^*$ corrupted by noise $E$, every CUR approximation variant considered obeys an error bound of the form a constant (depending on $I,J$) times $\|E\|$, plus higher-order terms. Concretely, Theorem 4.1 states $\|A-\tilde C\tilde C^\dagger\tilde A\tilde R^\dagger\tilde R\| \le \|E\|(\|W_{k,I}^\dagger\|+\|V_{k,J}^\dagger\|+3)$, where $W_{k,I}$ and $V_{k,J}$ are the row submatrices of the singular vectors selected by the row and column index sets. Analogous bounds are proved for the thresholded middle matrix $\tilde C[\tilde U]_\tau^\dagger \tilde R$, the rank-enforced middle matrix $\tilde C\tilde U_k^\dagger\tilde R$, and the projection-based rank-enforced approximation $\tilde C_k\tilde C_k^\dagger\tilde A\tilde R_k^\dagger\tilde R_k$. The paper also claims that maximal-volume selection of rows and columns converts the pseudoinverse constants into explicit universal factors, and that for non-SPSD matrices there is no provably best way to enforce the rank in a CUR approximation.

Load-bearing premise

The bounds collapse unless the selected columns and rows of the clean matrix $A$ already have rank exactly $k$, so the exact identities $A=CU^\dagger R$ and $A=CC^\dagger AR^\dagger R$ hold; the rank-enforced bound additionally assumes a spectral gap $\sigma_k(U)>2\mu\|E_{I,J}\|$.

Editorial extensions

If this is right

  • For the projection-based approximation, the error is at most $\|E\|(\|W_{k,I}^\dagger\|+\|V_{k,J}^\dagger\|+3)$, so accuracy is predictable from the noise size and the selected singular-vector submatrices alone.
  • Because the bounds hold for every Schatten $p$-norm simultaneously, one computation yields spectral, Frobenius, and nuclear error guarantees.
  • With maximal-volume selection, the pseudoinverse norms admit explicit universal upper bounds, turning the error estimate into constants that depend only on $k$ and the matrix dimensions.
  • For the rank-enforced variant on $\tilde U$, the error stays first-order in $\|E\|$ whenever $\sigma_k(U)>2\mu\|E_{I,J}\|$; outside that spectral-gap condition the stated bound does not apply.
  • For non-SPSD matrices, enforcing the rank after forming the CUR product is not provably better than enforcing it on the middle matrix, in contrast to the symmetric positive semidefinite case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step is to feed probabilistic bounds on $\|W_{k,I}^\dagger\|$ and $\|V_{k,J}^\dagger\|$ under leverage-score or other random sampling into these deterministic inequalities; the paper explicitly leaves that open.
  • The bounds suggest a concrete optimization objective for column and row selection: minimize $\|W_{k,I}^\dagger\|+\|V_{k,J}^\dagger\|$ over index sets, which quantifies selection quality even though exact maximal-volume selection is computationally hard.
  • The new projection-based rank-truncated variant $\tilde C_k\tilde C_k^\dagger\tilde A\tilde R_k^\dagger\tilde R_k$ deserves practical attention when only a little more than $k$ columns and rows are sampled, since the projection argument explains its favorable small-sample behavior.
  • Read back-to-front, the bounds can certify when CUR is competitive with truncated SVD: the index-set constant must be small compared with the inverse noise level.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper analyzes how CUR decompositions behave under additive noise, for a low-rank matrix A observed as A~=A+E. It derives perturbation bounds for five CUR approximation variants: the projection-based approximation C~C~†A~R~†R~, the non-projection approximation C~U~†R~ (with and without thresholding), rank enforcement on the middle matrix U, and a new projection-based rank-enforced variant. The bounds are expressed through the norms of pseudoinverses of submatrices of the truncated singular vectors W_k and V_k, hold for a broad class of unitarily invariant norms including all Schatten p-norms, and are linear in the noise norm with higher-order terms. The paper also refines the bounds under maximal-volume index selection, compares with prior work by Osinsky and Zamarashkin, gives a counterexample to rank-enforcement claims for non-SPSD matrices, and reports numerical experiments.

Significance. If the main theorems are taken together with their standing assumptions, the paper gives a systematic and largely self-contained perturbation theory for CUR decompositions. The proof structure is sound: the exact identities of Theorem 2.2, the norm identities of Proposition 6.4, and the Stewart-type pseudoinverse perturbation bounds are used carefully, and the new projection-based rank-enforced variant in Theorem 4.9 is a natural and useful contribution. The bounds are qualitative rather than probabilistic, which is appropriate for the goal of showing how the choice of rows and columns affects the error. The maximal-volume corollaries and the comparison with [31] are also informative. The main caveat is that every result is conditional on a full-rank assumption on the clean submatrices; the applicability of this assumption to index sets chosen from the noisy matrix is not addressed.

major comments (1)
  1. [Section 3.1, Theorems 4.1, 4.2, 4.6, 4.9] All main bounds are conditional on the standing assumption rank(C)=rank(U)=rank(R)=k for the clean matrix A. This is stated explicitly in Section 3.1, but it is the load-bearing hinge of the paper's central claim. In the motivating scenario, the index sets I and J are selected from the noisy matrix A~, yet no result or remark in the paper guarantees that those same sets produce full-rank submatrices of the unperturbed A. When the assumption fails, the bounds do not apply and the error need not be O(||E||) at all. For example, for a rank-1 matrix A=u v^T with v_j=0, choosing J to contain j gives U=0 for any I, while ~U=ε H_{I,J} is invertible with ||~U^†||≈1/ε; the product ~C~U^†~R does not converge to A as ε→0. The paper should either prove a transfer result showing that, for small noise, full rank of the selected submatrix of A~ implies (with high probability or under a mild condition) full rank of the corresponding submatrix of A, or it should explicitly restrict the claims in the abstract and introduction to index sets that make the clean submatrices full rank. Without such a clarification, the advertised noise-level guarantee is only valid for the very index sets that column-selection algorithms are trying to find.
minor comments (4)
  1. [Proposition 5.2] In the statement of Proposition 5.2, the definition of R should be A(I,:), not A(:,J); the current text contains a typo.
  2. [Section 9] In the numerical illustration, the phrase "the spectrum of A−CU^†_1R is approximately (100.9806, 1.9806, 0)" should refer to singular values rather than eigenvalues. The matrix A−CU^†_1R is not symmetric, and the actual eigenvalues include a negative value; the quantity relevant to Schatten p-norms is the singular values.
  3. [Section 5.2, comparison with Theorem 5.5] The comparison with Osinsky and Zamarashkin is made only for the square case |I|=|J|=k with the spectral norm. The paper should state more clearly that the claimed improvement over [31, Theorem 2] is restricted to that setting and does not address rectangular or oversampled cases.
  4. [Appendix B, Table B.1] The table is a useful summary, but the row for ~C~U~†~R uses w+v+3wv while Corollary 4.3 states w+v+3wv; the two should be checked for consistency. In the displayed Corollary 4.3 the coefficient is 3||W^†_{k,I}||||V^†_{k,J}||, which matches the table, so this is only a potential notation issue in the table header.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the perturbation bounds are proven from exact CUR identities and Stewart's pseudoinverse perturbation theorem, with no fitted constants or self-referential reductions.

full rationale

The derivation chain is transparent and non-circular. Under the standing assumption rank(C)=rank(U)=rank(R)=k, Theorem 2.2 (restated from the authors' prior work [23]) gives the exact identities A=CU†R and A=CC†AR†R. Every subsequent bound is obtained by expanding the difference between A and a noisy reconstruction using these identities, the triangle inequality, and submultiplicative unitarily invariant norms (Lemmas 8.1, Propositions 8.2 and 8.4, Lemma 8.7). Proposition 6.4, proved in Appendix A, converts the factors ‖CU†‖ and ‖U†R‖ into norms of pseudoinverses of submatrices of the singular vectors Wk,I and Vk,J; this is an algebraic identity, not a fitted quantity. Stewart's Theorem 7.2 supplies the pseudoinverse perturbation estimates, and the constants appearing in the bounds (3, mu in [1,3]) are universal and independent of the data. No parameter is tuned to a subset of the data and then renamed as a prediction; the theorems are worst-case inequalities valid for arbitrary noise under the stated rank condition. The paper's reliance on [23] for the exact CUR characterization is a normal citation of a published, independently checkable linear algebra result, and the present paper supplies its own proof of the key norm identity needed for the bounds. The rank assumption in Section 3.1 is explicitly stated; if it fails, the bounds do not apply, but the paper makes no contrary claim. That is a scope limitation, not circularity. Consequently, the central derivation is self-contained conditional on its stated assumptions, and there is no significant circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The analysis is built on a small number of structural assumptions: the low-rank-plus-noise model, a full-rank condition on the selected submatrices, and the standard norm class. No parameters are fitted to data; all constants come from cited theorems or from the matrices themselves. The paper adds no new postulated entities such as particles, forces, or dimensions.

assumptions (6)
  • domain assumption The observed matrix is ~A = A + E with rank(A) = k and E an arbitrary noise matrix.
    The entire perturbation analysis is structured around the low-rank-plus-noise model, introduced in Section 1.2 and used throughout the paper.
  • domain assumption The selected index sets I and J satisfy rank(C) = rank(U) = rank(R) = k.
    Stated in Section 3.1. This guarantees the exact CUR identities of Theorem 2.2 hold, so the perturbation bounds measure deviations from an exact decomposition. If this fails, the bounds do not apply.
  • standard math The norm under consideration is normalized, uniformly generated, unitarily invariant, and submultiplicative.
    Section 1.3 defines the norm class, which includes all Schatten p-norms. This is the technical setting for the Mirsky and Stewart theorems used in the proofs.
  • standard math Stewart's pseudoinverse perturbation theorem, Theorem 7.2, holds for this norm class with a universal constant mu between 1 and 3.
    Imported from [35]. It is used in Lemma 8.5 and Theorem 4.6. I have not machine-verified the general-norm version, but it is a standard citation.
  • standard math The exact CUR characterization, Theorem 2.2, from the authors' prior work [23] is correct.
    Cited from [23, Theorem 5.5]. It provides the algebraic identities A = CU^dagR and related identities on which the perturbation proofs are built. The result is published in a peer-reviewed journal, so it is an external benchmark for this paper.
  • standard math The maximal volume submatrix bounds of Osinsky and Zamarashkin, Proposition 5.1, are correct.
    Used in Section 5 to convert pseudoinverse norms into explicit t(k,m,|I|) factors. This is an independent external citation from [31].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Perturbations of CUR Decompositions." pith.science (2026). https://pith.science/paper/NQXQTL4Y

@misc{pith2026190808101,
  author       = {Pith},
  title        = {Pith review of: Perturbations of CUR Decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NQXQTL4Y}},
  note         = {Machine review of arXiv:1908.08101}
}
abstract

The CUR decomposition is a factorization of a low-rank matrix obtained by selecting certain column and row submatrices of it. We perform a thorough investigation of what happens to such decompositions in the presence of noise. Since CUR decompositions are non-uniquely formed, we investigate several variants and give perturbation estimates for each in terms of the magnitude of the noise matrix in a broad class of norms which includes all Schatten $p$--norms. The estimates given here are qualitative and illustrate how the choice of columns and rows affects the quality of the approximation, and additionally we obtain new state-of-the-art bounds for some variants of CUR approximations.

Figures

Figures reproduced from arXiv: 1908.08101 by the authors.

Figure 10.1
Figure 10.1. The performance of each rank-enforcement method for an SPSD matrix of rank 8 plus [PITH_FULL_IMAGE:figures/full_fig_p017_10_1.png] view at source ↗
Figure 10.2
Figure 10.2. The performances of each rank-enforcement method for a random matrix whose spectrum decays exponentially with decay parameter c = 0.1 (left) and c = 0.5 (right). The plot shows relative error in the spectral norm averaged over 20 trials vs. the number of columns and rows selected. Varying the exponential parameter and the power of the polynomial decay leads to qualitatively similar behavior, with faster decay of the… view at source ↗
Figure 10.3
Figure 10.3. The performances of each rank-enforcement method for a random matrix whose spectrum decays polynomially with the powers c = 1 (left) and c = 2 (right); the plot shows relative error in the spectral norm averaged over 20 trials vs. the number of columns and rows selected. setting Kij := e −kB(:,i)−B(:,j)k 2 . Then we repeat the process in Experiment 1 by testing the rank 40 CUR approximation of Ae and choosing x (the… view at source ↗
Figures from the paper (2 more)
Figure 10.4
Figure 10.4. Figure 10.4: (Left) The rank-8 CUR approximations of the Hopkins155 data matrix showing relative [PITH_FULL_IMAGE:figures/full_fig_p019_10_4.png]
Figure 10.5
Figure 10.5. Figure 10.5: The rank-10 CUR approximations of the Hilbert matrix [PITH_FULL_IMAGE:figures/full_fig_p021_10_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 42 canonical work pages

  1. [24]

    Hamm and L.-X

    K. Hamm and L.-X. Huang , Stability of sampling for CUR decompositions, Foundations of Data Science, 0 (2020), p. 0, https://doi.org/10.3934/fods.2020006, http://aimsciences.org//article/id/ f0aa05c7-97c8-40cb-8ecf-53f2c90f7069

    work page doi:10.3934/fods.2020006 2020

  2. [31]

    Osinsky and N

    A. Osinsky and N. L. Zamarashkin , Pseudo-skeleton approximations with better accuracy estimates, Linear Algebra and its Applications, 537 (2018), pp. 221–249

    work page 2018

  3. [1]

    Aldroubi, K

    A. Aldroubi, K. Hamm, A. B. Koku, and A. Sekmen, CUR decompositions, similarity matrices, and subspace clustering, Frontiers in Applied Mathematics and Statistics, 4 (2019), p. 65, https://doi.org/10.3389/fams. 2018.00065, https://www.frontiersin.org/article/10.3389/fams.2018.00065

    work page arXiv 2019

  4. [2]

    Benzi and V

    M. Benzi and V. Simoncini, Exploiting hidden structure in matrix computations: Algorithms and applications, Springer, 2015

    work page 2015

  5. [3]

    Boutsidis and D

    C. Boutsidis and D. P. Woodruff , Optimal CUR matrix decompositions, SIAM Journal on Computing, 46 (2017), pp. 543–589

    work page 2017

  6. [4]

    Bouwmans, S

    T. Bouwmans, S. Javed, H. Zhang, Z. Lin, and R. Otazo , On the applications of robust pca in image and video processing, Proceedings of the IEEE, 106 (2018), pp. 1427–1457

    work page 2018

  7. [5]

    Cand`es and J

    E. Cand`es and J. Romberg , Sparsity and incoherence in compressive sampling, Inverse problems, 23 (2007), p. 969

    work page 2007

  8. [6]

    E. J. Cand `es, X. Li, Y. Ma, and J. Wright , Robust principal component analysis?, Journal of the ACM (JACM), 58 (2011), pp. 1–37

    work page 2011

Show all 46 references
  1. [7]

    E. J. Cand`es and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), p. 717

    2009

  2. [8]

    Chiu and L

    J. Chiu and L. Demanet , Sublinear randomized algorithms for skeleton decompositions, SIAM Journal on Matrix Analysis and Applications, 34 (2013), pp. 1361–1383. PERTURBATIONS OF CUR DECOMPOSITIONS 23

    2013

  3. [9]

    Choi, Tricks or treats with the hilbert matrix, The American Mathematical Monthly, 90 (1983), pp

    M.-D. Choi, Tricks or treats with the hilbert matrix, The American Mathematical Monthly, 90 (1983), pp. 301– 312

    1983

  4. [10]

    Derezi´nski, R

    M. Derezi´nski, R. Khanna, and M. W. Mahoney , Improved guarantees and a multiple-descent curve for the column subset selection problem and the nystr\” om method, arXiv preprint arXiv:2002.09073, (2020)

    2020 arXiv

  5. [11]

    Drineas and I

    P. Drineas and I. C. Ipsen, Low-rank matrix approximations do not need a singular value gap, SIAM Journal on Matrix Analysis and Applications, 40 (2019), pp. 299–319

    2019

  6. [12]

    Drineas, R

    P. Drineas, R. Kannan, and M. W. Mahoney , Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition, SIAM Journal on Computing, 36 (2006), pp. 184–206

    2006

  7. [13]

    Drineas and M

    P. Drineas and M. W. Mahoney , On the Nystr¨ ommethod for approximating a Gram matrix for improved kernel-based learning, Journal of Machine Learning Research, 6 (2005), pp. 2153–2175

    2005

  8. [14]

    Drineas, M

    P. Drineas, M. W. Mahoney, and S. Muthukrishnan , Relative-error CUR matrix decompositions, SIAM Journal on Matrix Analysis and Applications, 30 (2008), pp. 844–881

    2008

  9. [15]

    Fazel, E

    M. Fazel, E. Candes, B. Recht, and P. Parrilo , Compressed sensing and robust recovery of low rank matrices, in 2008 42nd Asilomar Conference on Signals, Systems and Computers, IEEE, 2008, pp. 1043– 1047

    2008

  10. [16]

    Gittens and M

    A. Gittens and M. W. Mahoney , Revisiting the Nystr¨ ommethod for improved large-scale machine learning, The Journal of Machine Learning Research, 17 (2016), pp. 3977–4041

    2016

  11. [17]

    G. H. Golub and C. F. van Loan , Matrix Computations, The Johns Hopkins University Press, Baltimore, fourth ed., 2013

    2013

  12. [18]

    S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, How to find a good submatrix, in Matrix Methods: Theory, Algorithms And Applications: Dedicated to the Memory of Gene Golub, World Scientific, 2010, pp. 247–256

    2010

  13. [19]

    S. A. Gore˘ınov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudoskeleton approximations, Linear algebra and its applications, 261 (1997), pp. 1–21

    1997

  14. [20]

    S. A. Gore˘ınov, N. L. Zamarashkin, and E. E. Tyrtyshnikov, Pseudo-skeleton approximations of matrices, Dokl. Akad. Nauk, 343 (1995), pp. 151–152

    1995

  15. [21]

    S. A. Gore˘ınov, N. L. Zamarashkin, and E. E. Tyrtyshnikov, Pseudo-skeleton approximations by matrices of maximal volume, Mathematical Notes, 62 (1997), pp. 515–519

    1997

  16. [22]

    Halko, P.-G

    N. Halko, P.-G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53 (2011), pp. 217–288

    2011

  17. [23]

    Hamm and L.-X

    K. Hamm and L.-X. Huang , Perspectives on CUR decompositions, Applied and Computational Harmonic Analysis, 48 (2020), pp. 1088–1099

    2020

  18. [25]

    G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma , Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35 (2012), pp. 171–184

    2012

  19. [26]

    M. W. Mahoney and P. Drineas, CUR matrix decompositions for improved data analysis, Proceedings of the National Academy of Sciences, 106 (2009), pp. 697–702

    2009

  20. [27]

    Mikhalev and I

    A. Mikhalev and I. V. Oseledets, Rectangular maximum-volume submatrices and their applications, Linear Algebra and its Applications, 538 (2018), pp. 187–211

    2018

  21. [28]

    Mirsky, Symmetric gauge functions and unitarily invariant norms, The Quarterly Journal of Mathematics, 11 (1960), pp

    L. Mirsky, Symmetric gauge functions and unitarily invariant norms, The Quarterly Journal of Mathematics, 11 (1960), pp. 50–59

    1960

  22. [29]

    A. Y. Ng, M. I. Jordan, and Y. Weiss , On spectral clustering: Analysis and an algorithm, in Advances in neural information processing systems, 2002, pp. 849–856

    2002

  23. [30]

    Osinsky , Rectangular maximum volume and projective volume search algorithms, arXiv preprint arXiv:1809.02334, (2018)

    A. Osinsky , Rectangular maximum volume and projective volume search algorithms, arXiv preprint arXiv:1809.02334, (2018)

    2018 arXiv

  24. [32]

    V. Y. Pan, Q. Luan, J. Svadlenka, and L. Zhao , CUR low rank approximation of a matrix at sub-linear cost, arXiv preprint arXiv:1906.04112, (2019)

    2019 arXiv

  25. [33]

    Pourkamali-Anaraki and S

    F. Pourkamali-Anaraki and S. Becker, Improved fixed-rank Nystr¨ omapproximation via QR decomposition: Practical and theoretical aspects, Neurocomputing, (2019)

    2019

  26. [34]

    D. C. Sorensen and M. Embree, A DEIM induced CUR factorization, SIAM Journal on Scientific Computing, 38 (2016), pp. A1454–A1482

    2016

  27. [35]

    G. W. Stewart, On the perturbation of pseudo-inverses, projections and linear least squares problems, SIAM Review, 19 (1977), pp. 634–662, https://doi.org/10.1137/1019104, https://doi.org/10.1137%2F1019104

    1977 doi

  28. [36]

    G. W. Stewart, Perturbation theory for the singular value decomposition, tech. report, 1998. 24 KEATON HAMM AND LONGXIU HUANG

    1998

  29. [37]

    G. W. Stewart, Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix, Numerische Mathematik, 83 (1999), pp. 313–323

    1999

  30. [38]

    Tron and R

    R. Tron and R. Vidal, A benchmark for the comparison of 3-d motion segmentation algorithms, in Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE Conference on, IEEE, 2007, pp. 1–8

    2007

  31. [39]

    J. A. Tropp , Improved analysis of the subsampled randomized hadamard transform, Advances in Adaptive Data Analysis, 3 (2011), pp. 115–126

    2011

  32. [40]

    J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Fixed-rank approximation of a positive-semidefinite matrix from streaming data, in Advances in Neural Information Processing Systems, 2017, pp. 1225–1234

    2017

  33. [41]

    J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher , Streaming low-rank matrix approximation with an application to scientific simulation, arXiv preprint arXiv:1902.08651, (2019)

    2019 arXiv

  34. [42]

    Tyrtyshnikov, Kronecker-product approximations for some function-related matrices, Linear Algebra and its Applications, 379 (2004), pp

    E. Tyrtyshnikov, Kronecker-product approximations for some function-related matrices, Linear Algebra and its Applications, 379 (2004), pp. 423–437

    2004

  35. [43]

    Udell and A

    M. Udell and A. Townsend , Why are big data matrices approximately low rank?, SIAM Journal on Mathe- matics of Data Science, 1 (2019), pp. 144–160

    2019

  36. [44]

    Voronin and P.-G

    S. Voronin and P.-G. Martinsson , Efficient algorithms for CUR and interpolative matrix decompositions, Advances in Computational Mathematics, 43 (2017), pp. 495–516

    2017

  37. [45]

    S. Wang, A. Gittens, and M. W. Mahoney, Scalable kernel k-means clustering with Nystr¨ omapproximation: Relative-error bounds, Journal of Machine Learning Research, 20 (2019), pp. 1–49

    2019

  38. [46]

    Wang and A

    Y. Wang and A. Singh, Provably correct algorithms for matrix column subset selection with selectively sampled data, Journal of Machine Learning Research, 18 (2017), pp. 5699–5740. PERTURBATIONS OF CUR DECOMPOSITIONS 25 Appendix A. Proof of Proposition 6.4. First, note that by ...

    2017

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.