Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Fast exact recovery of noisy matrix from few entries: the infinity norm approach

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read A simple truncated-SVD-plus-rounding algorithm recovers every entry of a noisy low-rank matrix exactly, under the three standard assumptions plus a large-signal condition.

desk verdict Real result, oversold abstract: the large-signal condition is load-bearing but mild, and the proof is worth engaging. read the letter →

arxiv 2501.19224 v2 pith:BXP66B3T submitted 2025-01-31 math.ST cs.LGmath.COmath.PRstat.APstat.TH

BaoLinh Tran , Van Vu This is my paper · ORCID
classification math.STcs.LGmath.COmath.PRstat.APstat.TH MSC 15A1815A4260B2062H12
keywords matrixcompletionexactrecoveryinfinitynormDavis-Kahan-Wedintheoremlow-rankperturbationnoisyobservationsrandomsamplingsingularvaluethresholding
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

This paper claims that exact recovery of a low-rank matrix from a small random sample of noisy entries can be achieved by a single truncated singular value decomposition followed by rounding, under only the three standard assumptions of the field: low rank, incoherent (delocalized) singular vectors, and sufficiently dense sampling. Previous algorithms that achieved exact recovery in the noisy setting needed an extra spectral condition, either a bounded condition number or large gaps between consecutive singular values; this work removes both. The price is a large-signal condition on the top singular value, which the paper argues is mild and often automatic. If the claim is right, the practical consequence is that the simplest possible pipeline, estimate density, rescale, truncate, round, provably recovers every entry of a bounded-precision matrix with high probability.

What carries the argument

The central object is the new infinity-norm Davis-Kahan-Wedin theorem (Theorem 3.2). It bounds $\|\tilde{A}_s - A_s\|_\infty$ by $C \tau_1 \tau_2 \sigma_s r (\|E\|/\sigma_s + 2r\|U^T E V\|_\infty/\delta_s + 2r y/(\delta_s \sigma_s))$, where the $\tau$'s are coherence parameters of the interaction between the noise and the singular vectors, $\delta_s$ is the singular-value gap, and $y$ measures the size of diagonal blocks of $E E^T$ in the singular basis. The proof machinery is a resolvent contour-integral expansion: after symmetrizing the SVD, the difference of spectral projectors is written as a power series in the noise, each term of which is a product of monomials whose integral coefficients are bounded by contour-integral estimates; a combinatorial walk-counting argument controls the sum, and the series is summed geometrically. The random version (Theorem 3.3) uses new semi-isotropic bounds for powers of random matrices to convert the deterministic $\tau$'s into explicit polylogarithmic factors.

What would settle it

Numerically evaluate the ratio $\|\tilde{A}_s - A_s\|_\infty / \big[\sigma_s r (\|E\|/\sigma_s + 2r\|U^T E V\|_\infty/\delta_s + 2r y/(\delta_s \sigma_s))\big]$ over a large set of random low-rank $A$ and Gaussian $E$ with $r=2$, $m=n=10^3$. If the supremum of this ratio exceeds the universal constant in Theorem 3.2 by more than a small factor, the new Davis-Kahan-Wedin bound is violated, and a single such violation with fixed dimensions, verified by exact arithmetic, would settle the claim.

Watch

Extended reading notes

Core claim

The paper proves (Theorem 1.5) that, under low rank $r \le \log^2 N$, incoherence $\mu_0$, sampling density (19), bounded finite-precision entries and bounded noise, and the large-signal bound $\sigma_1 \ge 100 r K \sqrt{r_{\max} N / p}$, the first three steps of the algorithm AR2 return a matrix $\tilde{A}_s$ with $\|\tilde{A}_s - A\|_\infty \le \varepsilon_0/3$ with probability $1 - O(N^{-1})$; rounding to the nearest multiple of $\varepsilon_0$ then recovers $A$ exactly. The algorithm needs only an upper bound on the rank, not the rank itself: the truncation index $s$ is chosen as the largest gap of the rescaled observed matrix above a threshold. The mathematical core is a new infinity-norm perturbation theorem (Theorem 3.2), an analogue and extension of the Davis-Kahan-Wedin theorem, which bounds how much the best rank-$s$ approximation of $A+E$ moves in the infinity norm as a function of the noise $E$, the interlacing term $U^T E V$, and coherence-type parameters $\tau_1, \tau_2$, under a condition on the noise-to-gap ratio.

Load-bearing premise

The load-bearing premise is the large-signal condition $\sigma_1 \ge 100 r K \sqrt{r_{\max} N / p}$: if the top singular value falls below this level, the argument that a valid truncation index $s \le r$ exists and that the tail $\sigma_{s+1}$ is small collapses, so the infinity-norm guarantee no longer follows.

Editorial extensions

If this is right

  • Exact noisy completion becomes a one-pass truncated-SVD plus rounding procedure; no iterative cleaning and no exact knowledge of the rank are required, only an upper bound $r_{\max}$.
  • The sampling density bound in the base case is $O(N \log^{10} N)$ with no factor of the condition number, matching earlier noiseless spectral bounds up to polylogarithmic factors.
  • The large-signal condition is the only new formal requirement; the paper argues it is usually implied by normalization and the classical phase-transition threshold for random perturbations.
  • The deterministic infinity-norm perturbation bound is a standalone matrix-analysis result, applicable beyond matrix completion whenever a low-rank matrix is perturbed by bounded-moment noise.

Reading between the lines

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

  • The paper's phrase 'only three basic assumptions' is slightly generous: the large-signal premise is an additional formal assumption, although it is a signal-to-noise floor rather than a spectral-shape condition, and may be information-theoretically unavoidable.
  • A natural stress test is to run AR2 with several equal large singular values (zero gap) and $\sigma_1$ at the stated threshold; the cutoff rule should still select a valid $s$, but the numerical margin is likely thin near the boundary of the sampling condition.
  • The semi-isotropic power bounds for random matrices (Lemma 4.2) appear reusable for entrywise eigenvector or singular-vector analyses in other settings, such as community detection or spectral clustering.
  • The deterministic Theorem 3.2 replaces incoherence with a general condition on the noise and the singular vectors; identifying natural non-random perturbations that satisfy this condition could widen the theorem's range.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. This paper studies exact matrix completion from noisy, partially observed entries, assuming the ground-truth matrix has entries at finite precision (multiples of ε0). The authors propose the algorithm AR2, which rescales the observed matrix, computes a truncated SVD with a data-dependent cutoff, and rounds the result to the nearest multiple of ε0. The main theorem (Theorem 1.5) asserts that, under low rank, incoherence, the sampling-density condition (19), bounded noise moments, and a large-signal condition σ1 ≥ 100 r K sqrt(rmax N / p), the first three steps of AR2 approximate A entrywise to error ε0/3 with probability 1 - O(N^{-1}), so rounding then recovers A exactly. The proof builds on a new infinity-norm Davis-Kahan-Wedin-type perturbation bound (Theorem 3.2), a random version (Theorem 3.3), and a deduction chain from Theorem 2.1 to Theorem 1.5. The paper advertises removal of the extra spectral assumptions (small condition number or large singular-value gaps) required by previous infinity-norm approaches.

Significance. If the proof chain is completed, this is a significant contribution: it would give the first noisy exact-recovery result using essentially the classical low-rank, incoherence, and sampling-density assumptions, with an extremely simple algorithm (truncated SVD plus rounding). The contour-integration and combinatorial-expansion method for infinity-norm perturbation bounds is new and appears to be of independent interest; the sequence from the deterministic Theorem 3.2 through the random Theorem 3.3 to Theorem 2.1 and Theorem 1.5 is presented in detailed, largely self-contained fashion, including semi-isotropic moment bounds for powers of random matrices. However, the advertised claim of recovery 'under only the three basic assumptions' is not literally what is proved, and the proof of the key Lemma 4.2 is currently incomplete as written. Both issues are load-bearing and must be addressed before the central claims can be taken at face value.

major comments (3)
  1. [Abstract, §1.7.3, Theorem 1.5] The abstract and the introduction state that exact recovery is achieved 'under only the three basic assumptions' (low rank, incoherence, density), but Theorem 1.5 contains an additional hypothesis, the large-signal condition σ1 ≥ 100 r K sqrt(rmax N / p) with K = K_A + K_Z. This condition is not cosmetic: the proof of Theorem 1.5 uses it to find an index l ∈ [r] with δ_l ≥ σ1/r, so that Weyl's inequality yields a gap above the algorithm's cutoff and ensures the selected index s lies in [r]; it is also used to control σ_{s+1} in Eq. (31), which is needed to bound ∥A_s − A∥∞. Remark 1.7.3 concedes 'Well, almost!' and argues that the condition is mild and often automatic, but mildness does not make it one of the three basic assumptions. The abstract and Section 1.7 should be qualified to state 'the three basic assumptions plus a large-signal condition,' and the remark should be integrated into the statement of the main theorem rather than left as an aside.
  2. [§B.2, proof of Lemma 4.2] The proof of Lemma 4.2 is incomplete as written. After the sentence 'We follow two steps:', the text breaks off at '1. Assuming M' and then resumes with 'Consider the analogue of Eq. (52) for V (we wrote the proof for V before the final edit, and wanted to save the energy of changing to U)' without completing the normalization from general ς to the case ς = 1, without specifying the constants D used in the applications of Lemmas B.3 and B.4, and without treating the stated range t > 0 and the two probability regimes in Eqs. (52)–(53) versus Eqs. (54)–(55). Since Lemma 4.2 supplies the semi-isotropic bounds for τ1 and τ2 used in the proof of Theorem 3.3, and Theorem 3.3 is the bridge to Theorem 2.1 and Theorem 1.5, this gap is load-bearing. The full proof needs to be supplied.
  3. [§3.2, end of Section 3.2] The proof-structure discussion at the end of Section 3.2 states that 'we need to dedicate the whole Section 5 for the proof of Theorem 3.3', but the proof of Theorem 3.3 actually appears in Section 4.1. The cross-reference should be corrected, and the structural roadmap should be updated to match the actual section numbering.
minor comments (4)
  1. [§3.2] The sentence about recent universality results contains the placeholder 'cite Y au et al book which you read'; this must be replaced with a proper citation or removed.
  2. [Theorem 1.5] The phrase 'if all entries are multiples integer of ε0' should read 'if all entries are integer multiples of ε0'.
  3. [§4.2] The text near Eq. (67) says 'bounding it with overwhelming probablity'; the typo 'probablity' should be corrected to 'probability'.
  4. [§2.2] In the proof of Theorem 1.5, the probability bound for the concentration of ρ is stated as 1 − O(N^{-2}), while the final theorem claims 1 − O(N^{-1}); the proof should clarify that the union bound over all stages still leaves the O(N^{-1}) rate.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the abstract's 'only three basic assumptions' overstates Theorem 1.5's formal hypotheses, but the proof chain is self-contained and no fitted quantity is renamed as a prediction.

full rationale

Walking the derivation chain: Theorem 1.5 is proved from Theorem 2.1, which follows from Theorem 3.3 via Theorem 3.2; Theorem 3.2 is proved in Sections 4.2-4.4 using Lemma 4.4 and supporting Lemmas 4.6-4.9, with Appendix B proving the contour-integral and semi-isotropic bounds. The algorithm's cutoff and the large-signal condition are used to prove the existence of an index s in [r] with a singular-value gap above the cutoff (the argument gives delta_hat_l >= 80 K sqrt(rmax N / p_hat) and delta_hat_{r+1} < 20 K sqrt(rmax N / p_hat)); this is a genuine sufficient condition, not a parameter fitted to the target matrix and then renamed as a prediction. The separation delta_l >= sigma_1 / r is derived from low rank and then used to choose the cutoff, which is a real argument. The main caveat is that the abstract's claim of 'only three basic assumptions' is not literally supported by Theorem 1.5, which formally adds the 'Large signal' hypothesis sigma_1 >= 100 r K sqrt(rmax N / p); Remark 1.7.3 concedes 'Well, almost!' and argues the condition is mild and often automatic. This is a scope/accuracy qualification rather than circularity. The paper relies on the authors' prior machinery in [6], [38], and [39] for contour expansions and walk counting, but it presents the full proofs of the new infinity-norm bounds, so those citations are not load-bearing in a circular way. Overall circularity is low.

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

No numbers are fitted to data. K_A, K_Z, epsilon_0, and rmax are inputs, and all constants are universal. The central claim depends on the listed standard tools and on the explicit modeling assumptions, the most consequential being the large-signal condition that the abstract omits.

assumptions (9)
  • standard math SVD and resolvent contour identities used in Setting 4.3 and Eqs. (56)-(58)
    Standard linear algebra: symmetrization of SVD to eigendecomposition and resolvent expansions.
  • standard math Weyl's inequality and classical Davis-Kahan-Wedin spectral bounds
    Used throughout Sections 2 and 3 to control singular value movement and eigenspace perturbation.
  • standard math Random matrix norm concentration, including ||E|| <= 1.9 sigma sqrt(m+n)
    Invoked via Lemma 4.1; these are external theorems from [39] and [3], not proved in this paper.
  • standard math Coding scheme and walk-counting bounds of Vu [39]
    Used in Appendix B.2 to bound semi-isotropic moments of powers of random matrices.
  • domain assumption Low rank, incoherence mu_0, and sampling density condition (19)
    These are the three basic assumptions of the matrix completion model.
  • domain assumption Finite precision: entries of A are integer multiples of epsilon_0 and bounded by K_A with known K_A
    Needed to justify rounding; exact recovery is otherwise impossible for irrational entries.
  • domain assumption Noise Z has independent centered entries with all moments bounded by K_Z, with known K_Z
    Moment bounds feed the semi-isotropic bounds and Bernstein concentration in Lemma 4.1.
  • domain assumption Large signal condition sigma_1 >= 100 r K sqrt(rmax N / p)
    Extra fourth assumption in Theorem 1.5, argued necessary by the BBP phase transition; not one of the three basic assumptions.
  • domain assumption rmax <= log^2 N in the main theorem
    Restricts the rank upper bound; the appendix removes it with a stronger density bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast exact recovery of noisy matrix from few entries: the infinity norm approach." pith.science (2026). https://pith.science/paper/BXP66B3T

@misc{pith2026250119224,
  author       = {Pith},
  title        = {Pith review of: Fast exact recovery of noisy matrix from few entries: the infinity norm approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BXP66B3T}},
  note         = {Machine review of arXiv:2501.19224}
}
abstract

The matrix recovery (completion) problem, a central problem in data science and theoretical computer science, is to recover a matrix $A$ from a relatively small sample of entries. While such a task is impossible in general, it has been shown that one can recover $A$ exactly in polynomial time, with high probability, from a random subset of entries, under three (basic and necessary) assumptions: (1) the rank of $A$ is very small compared to its dimensions (low rank), (2) $A$ has delocalized singular vectors (incoherence), and (3) the sample size is sufficiently large. There are many different algorithms for the task, including convex optimization by Candes, Tao and Recht (2009), alternating projection by Hardt and Wooters (2014) and low rank approximation with gradient descent by Keshavan, Montanari and Oh (2009, 2010). In applications, it is more realistic to assume that data is noisy. In this case, these approaches provide an approximate recovery with small root mean square error. However, it is hard to transform such an approximate recovery to an exact one. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) concerning approximation in the infinity norm showed that we can achieve exact recovery even in the noisy case, given that the ground matrix has bounded precision. Beyond the three basic assumptions above, they required either the condition number of $A$ is small (Abbe et al.) or the gap between consecutive singular values is large (Bhardwaj et al.). In this paper, we remove these extra spectral assumptions. As a result, we obtain a simple algorithm for exact recovery in the noisy case, under only the three basic assumptions. This is the first such algorithm. To analyse this algorithm, we introduce a contour integration argument which is totally different from all previous methods and may be of independent interest.

Figures

Figures reproduced from arXiv: 2501.19224 by the authors.

Figure 1
Figure 1. The Yale face database [40] has 165 greyscale face images of dimension 243 ×320, which can be turned into vectors in R 77760 and arranged onto a matrix in R 77760×165. Center this matrix by subtracting from every column their average. Shown above are the first 30 singular values and first 30 consecutive singular value gaps of this centered matrix. The picture on the left shows that matrix has a small numer of large … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Estimating eigenvectors and eigenspaces of covariance matrices: Optimal Bounds and Conditions for Consistency

    math.ST 2026-07 conditional novelty 6.0 of 10

    Sample-covariance eigenvector and eigenspace errors are determined up to constant factors by the effective rank and the signal-to-gap ratio, giving near-optimal consistency thresholds.

Reference graph

Works this paper leans on

41 extracted references · 39 canonical work pages · cited by 1 Pith paper

  1. [38]

    Phuc Tran and Van Vu, New matrix perturbation bounds via combinatorial expansion i: Per- turbation of eigenspaces, arXiv preprint https://arxiv.org/abs/2409.20207

    arXiv

  2. [1]

    Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong, Entrywise eigenvector analysis of random matrices with low expected rank , Ann. Statist. 48 (2020), no. 3, 1452–1474. MR 4124330

    work page 2020

  3. [2]

    Jinho Baik, G´ erard Ben Arous, and Sandrine P´ ech´ e,Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices , Ann. Probab. 33 (2005), no. 5, 1643–1697. MR 2165575

    work page 2005

  4. [3]

    Bandeira and Ramon van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries , Ann

    Afonso S. Bandeira and Ramon van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries , Ann. Probab. 44 (2016), no. 4, 2479–2506. MR 3531673

    work page 2016

  5. [4]

    Bell and Yehuda Koren, Lessons from the netflix prize challenge , SIGKDD Explor

    Robert M. Bell and Yehuda Koren, Lessons from the netflix prize challenge , SIGKDD Explor. Newsl. 9 (2007), no. 2, 75–79

    work page 2007

  6. [5]

    Florent Benaych-Georges and Raj Rao Nadakuditi, The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices , Adv. Math. 227 (2011), no. 1, 494–521. MR 2782201

    work page 2011

  7. [6]

    Abhinav Bhardwaj and Van Vu, Matrix perturbation: Davis-Kahan in the infinity norm , Pro- ceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2024, pp. 880–934. MR 4699279

    work page 2024

  8. [7]

    Cand` es, and Zuowei Shen,A singular value thresholding algorithm for matrix completion , SIAM J

    Jian-Feng Cai, Emmanuel J. Cand` es, and Zuowei Shen,A singular value thresholding algorithm for matrix completion , SIAM J. Optim. 20 (2010), no. 4, 1956–1982. MR 2600248

    work page 2010

Show all 41 references
  1. [8]

    3, 969–985

    Emmanuel Cand` es and Justin Romberg, Sparsity and incoherence in compressive sampling , Inverse Problems 23 (2007), no. 3, 969–985. MR 2329927 57

    2007

  2. [9]

    Cand` es and Yaniv Plan,Matrix completion with noise , Proceedings of the IEEE 98 (2010), no

    Emmanuel J. Cand` es and Yaniv Plan,Matrix completion with noise , Proceedings of the IEEE 98 (2010), no. 6, 925–936

    2010

  3. [10]

    Cand` es and Benjamin Recht,Exact matrix completion via convex optimization , Found

    Emmanuel J. Cand` es and Benjamin Recht,Exact matrix completion via convex optimization , Found. Comput. Math. 9 (2009), no. 6, 717–772. MR 2565240

    2009

  4. [11]

    Cand` es and Terence Tao,The power of convex relaxation: near-optimal matrix completion, IEEE Trans

    Emmanuel J. Cand` es and Terence Tao,The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inform. Theory 56 (2010), no. 5, 2053–2080. MR 2723472

    2010

  5. [12]

    Mireille Capitaine, Catherine Donati-Martin, and Delphine F´ eral, The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluc- tuations, Ann. Probab. 37 (2009), no. 1, 1–47. MR 2489158

    2009

  6. [13]

    Sourav Chatterjee, Matrix estimation by universal singular value thresholding , Ann. Statist. 43 (2015), no. 1, 177–214. MR 3285604

    2015

  7. [14]

    Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations , Ann. Math. Statistics 23 (1952), 493–507. MR 57518

    1952

  8. [15]

    A. L. Chistov and D. Yu. Grigor’ev, Complexity of quantifier elimination in the theory of algebraically closed fields, Mathematical foundations of computer science, 1984 (Prague, 1984), Lecture Notes in Comput. Sci., vol. 176, Springer, Berlin, 1984, pp. 17–31. MR 783435

    1984

  9. [16]

    Davenport and Justin Romberg, An overview of low-rank matrix recovery from in- complete observations, IEEE Journal of Selected Topics in Signal Processing 10 (2016), no

    Mark A. Davenport and Justin Romberg, An overview of low-rank matrix recovery from in- complete observations, IEEE Journal of Selected Topics in Signal Processing 10 (2016), no. 4, 608–622

    2016

  10. [17]

    Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III , SIAM J. Numer. Anal. 7 (1970), 1–46. MR 264450

    1970

  11. [18]

    Donoho, Compressed sensing, IEEE Trans

    David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–

    2006

  12. [19]

    Delphine F´ eral and Sandrine P´ ech´ e,The largest eigenvalue of rank one deformation of large Wigner matrices, Comm. Math. Phys. 272 (2007), no. 1, 185–228. MR 2291807

    2007

  13. [20]

    Farzan Haddadi and Arash Amini, Eigenvectors of deformed Wigner random matrices , IEEE Trans. Inform. Theory 67 (2021), no. 2, 1069–1079. MR 4232001

    2021

  14. [21]

    Moritz Hardt, Understanding alternating minimization for matrix completion , 55th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2014, IEEE Computer Soc., Los Alamitos, CA, 2014, pp. 651–660. MR 3344916

    2014

  15. [22]

    35, PMLR, 13–15 Jun 2014, pp

    Moritz Hardt and Mary Wootters, Fast matrix completion without the condition number , Pro- ceedings of The 27th Conference on Learning Theory (Barcelona, Spain) (Maria Florina Bal- can, Vitaly Feldman, and Csaba Szepesv´ ari, eds.), Proceedings of Machine Learning Research, vo...

    2014

  16. [23]

    Wassily Hoeffding, Probability inequalities for sums of bounded random variables , J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363

    1963

  17. [24]

    Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi, Low-rank matrix completion using alternating minimization (extended abstract) , STOC’13—Proceedings of the 2013 ACM Sym- posium on Theory of Computing, ACM, New York, 2013, pp. 665–674. MR 3210828 58

    2013

  18. [25]

    Keshavan, Andrea Montanari, and Sewoong Oh, Matrix completion from a few entries , IEEE Trans

    Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh, Matrix completion from a few entries , IEEE Trans. Inform. Theory 56 (2010), no. 6, 2980–2998. MR 2683452

    2010

  19. [26]

    , Matrix completion from noisy entries , J. Mach. Learn. Res. 11 (2010), 2057–2078. MR 2678022

    2010

  20. [27]

    Keshavan and Sewoong Oh, A gradient descent algorithm on the grassman manifold for matrix completion , 2009, arXiv preprint https://arxiv.org/abs/0910.5260

    Raghunandan H. Keshavan and Sewoong Oh, A gradient descent algorithm on the grassman manifold for matrix completion , 2009, arXiv preprint https://arxiv.org/abs/0910.5260

    2009 arXiv

  21. [28]

    Xiao Peng Li, Lei Huang, Hing Cheung So, and Bo Zhao, A survey on matrix completion: Perspective of signal processing, 2019, arXiv preprint https://arxiv.org/abs/1901.10885

    2019 arXiv

  22. [29]

    2, 215–245

    Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215–245. MR 1337355

    1995

  23. [30]

    Mesbahi and G

    M. Mesbahi and G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Trans. Automat. Control42 (1997), no. 2, 239–243. MR 1438452

    1997

  24. [31]

    540 (2018), 26–59

    Sean O’Rourke, Van Vu, and Ke Wang, Random perturbation of low rank matrices: improving classical bounds, Linear Algebra Appl. 540 (2018), 26–59. MR 3739989

    2018

  25. [32]

    Theory Related Fields 134 (2006), no

    Sandrine P´ ech´ e,The largest eigenvalue of small rank perturbations of Hermitian random ma- trices, Probab. Theory Related Fields 134 (2006), no. 1, 127–173. MR 2221787

    2006

  26. [33]

    Benjamin Recht, A simpler approach to matrix completion , J. Mach. Learn. Res. 12 (2011), 3413–3430. MR 2877360

    2011

  27. [34]

    Anthony Man-Cho So and Yinyu Ye, Theory of semidefinite programming for sensor network localization, Math. Program. 109 (2007), no. 2-3, 367–384. MR 2295148

    2007

  28. [35]

    Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones , Optim

    Jos F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones , Optim. Methods Softw. 11/12 (1999), no. 1-4, 625–653, Interior point methods. MR 1778433

    1999

  29. [36]

    K. C. Toh, M. J. Todd, and R. H. T¨ ut¨ unc¨ u,SDPT3—a MATLAB software package for semidef- inite programming, version 1.3 , Optim. Methods Softw. 11/12 (1999), no. 1-4, 545–581, Inte- rior point methods. MR 1778429

    1999

  30. [37]

    power of few

    BaoLinh Tran and Van Vu, The “power of few” phenomenon: the sparse case , Random Struc- tures Algorithms 66 (2025), no. 1, Paper No. e21260, 16. MR 4827408

    2025

  31. [39]

    6, 721–736

    Van Vu, Spectral norm of random matrices , Combinatorica 27 (2007), no. 6, 721–736. MR 2384414

    2007

  32. [40]

    Wainwright, Principal component analysis in high dimensions , Cambridge Series in Statistical and Probabilistic Mathematics, p

    Martin J. Wainwright, Principal component analysis in high dimensions , Cambridge Series in Statistical and Probabilistic Mathematics, p. 236–258, Cambridge University Press, 2019

    2019

  33. [41]

    Informationsbehandling (BIT) 12 (1972), 99–111

    Per- ˙Ake Wedin, Perturbation bounds in connection with singular value decomposition , Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 99–111. MR 309968 59

    1972

Pith tools

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