Pith. sign in

REVIEW 2 major objections 3 minor 86 references

Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations

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

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

Pith's one-line read A complex Gaussian mechanism analyzed through Dyson Brownian motion achieves an (ε,δ)-private rank-k covariance approximation whose expected Frobenius error is O~(√(kd)·σ_k/(σ_k−σ_{k+1})·√(log(1/δ))/ε), improving prior Gaussian-mechanism…

desk verdict Real technique, real flaw: the rank-k claim in Theorem 2.2 is false, but the Dyson Brownian motion machinery and eigenvalue-gap bound deserve a referee. read the letter →

arxiv 2502.07657 v1 pith:NUO4U7DX submitted 2025-02-11 cs.DS cs.CRcs.LGcs.NAmath.NAmath.PR

Oren Mangoubi , Nisheeth K. Vishnoi This is my paper · ORCID
classification cs.DScs.CRcs.LGcs.NAmath.NAmath.PR MSC 60B2015B5268P2760J6562H25
keywords differentialprivacylow-rankapproximationcovariancematrixGaussianmechanismDysonBrownianmotioneigenvaluegapsUnitaryEnsemblerandomtheory
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 sets out to prove that a complex version of the Gaussian mechanism can release a rank-k approximation of a covariance matrix that is simultaneously (ε,δ)-differentially private and, in expected Frobenius error, roughly √(kd)·σ_k/(σ_k−σ_{k+1})·√(log(1/δ))/ε away from the best rank-k approximation. When the k-th eigenvalue gap is Ω(σ_k), that would beat the previous Gaussian-mechanism bound by a factor of about √k, and the mechanism is private for free because it post-processes the real Gaussian mechanism. The central technical claim is that the analysis can be carried out by viewing the added noise as matrix Brownian motion, so that eigenvalues and eigenvectors evolve by Dyson Brownian motion and the change in the best rank-k approximation becomes an integral over inverse eigenvalue gaps rather than a sum of Davis-Kahan-type bounds. To keep those integrals finite the paper proves a new eigenvalue-gap estimate, P(gap ≤ s/(b√d)) ≤ $s^{{β+1}}$ + $d^{{−1000}}$ with β=2 for complex noise and β=1 for real noise, improving the previously known s² decay in the complex case. These gap bounds and the diffusion viewpoint are claimed as contributions beyond privacy, with use for average-case perturbation analysis and random matrix theory.

What carries the argument

The load-bearing object is Dyson Brownian motion: the stochastic differential equations dγ_i(t) = dB_ii(t) + β Σ_{j≠i} dt/(γ_i(t)−γ_j(t)) for the eigenvalues of a Hermitian matrix undergoing Brownian perturbation, together with the companion stochastic differential equation for the eigenvector flow. The paper's second central object is the rank-k matrix diffusion Ψ(t) = U(t)Λ(t)U(t)* whose eigenvalues track the top k eigenvalues of the diffusing matrix in real time (λ_i(t)=γ_i(t) for i≤k, else 0); this tracking cancels the dominant inverse-gap singularities in the Itô integral for E‖Ψ(T)−Ψ(0)‖²_F, reducing the bound to second moments of inverse gaps. The gap estimates themselves are proved by a comparison lemma (Lemma 4.2) showing that gaps of a coupled Dyson Brownian motion dominate gaps from the zero initial condition, and by injective spectrum maps g and φ that push a small eigenvalue gap apart inside the joint GUE density ∏_{i<j}|η_i−η_j|^β $e^{{−½Ση_j²}}$, trading the small-gap probability against a Jacobian factor and a density ratio to reach $s^{{β+1}}$ decay.

What would settle it

Check the rank premise directly: for the unit vector u=(1,i)/√2 in C², the rank-1 Hermitian matrix uu* has real part (1/2)I₂, a real matrix of rank 2. Equivalently, run Algorithm 1 on any input and compute the rank of Y = Real(V̂Σ̂_kV̂*); observing rank(Y) > k with positive probability settles that the output is not necessarily a rank-k matrix as Theorem 2.2 requires.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that replacing real Gaussian noise by complex Gaussian noise turns the private low-rank approximation problem into a Dyson Brownian motion calculation. Theorem 2.3 states that under the eigengap assumption σ_k−σ_{k+1} ≥ 4√(Td) and σ_1 ≤ $d^{{50}}$, the expected squared Frobenius distance between the best rank-k approximation of a Hermitian matrix M and that of its complex Gaussian perturbation M̂ = M + √T(W+W*) is O~(kd·σ_k²/(σ_k−σ_{k+1})²)·T. The proof defines a rank-k matrix-valued process Ψ(t) whose eigenvectors are the eigenvectors of the diffusing matrix and whose eigenvalues are λ_i(t)=γ_i(t) for i≤k and 0 otherwise, so that at time T it equals the rank-k truncation of the perturbed matrix and at time 0 the rank-k truncation of M; Itô calculus expresses the expected squared change of Ψ as an integral of inverse-eigengap terms, and the dynamically chosen eigenvalues cancel the strongest singularities, leaving only second moments of inverse gaps. Theorem 2.4 supplies the missing gap control: gaps of GUE/GOE-type perturbations decay as $s^{{β+1}}$ in probability, and the comparison Lemma 4.2 shows that gaps from any initial condition dominate gaps from the zero initial condition when both processes are coupled to the same Brownian motion. From these the paper derives Theorem 2.2, the private approximation guarantee of Algorithm 1, together with a subspace-recovery analogue and an eigengap-free bound in a weaker Frobenius metric.

Load-bearing premise

The proof of the main theorem assumes that the real part of the complex Hermitian rank-k matrix computed from the noisy spectrum is itself a real matrix of rank at most k, so that the output of Algorithm 1 is a genuine rank-k matrix; general rank-k Hermitian matrices have real parts of rank up to 2k, and if that premise fails the stated rank and error guarantee do not follow.

Editorial extensions

If this is right

  • Algorithm 1 is (ε,δ)-differentially private as a post-processing of the real Gaussian mechanism, so the entire contribution of the paper lies in the utility analysis rather than in a new privacy argument.
  • If Theorem 2.2's bound holds, the expected Frobenius error of the private rank-k output is O~(√(kd) · σ_k/(σ_k−σ_{k+1}) · √(log(1/δ))/ε), improving on the previous Gaussian-mechanism bound by about √k whenever σ_k−σ_{k+1} = Ω(σ_k).
  • The same diffusion analysis yields a private subspace-recovery bound of O~(√(Σ_{i≤k, j>k} 1/(σ_i−σ_j)²)) · √T, which beats Davis-Kahan-based bounds for spectra with well-spread gaps.
  • Eigenvalue gaps of complex Gaussian perturbations satisfy P(gap ≤ s/(b√d)) ≤ s³ + d^{−1000}; this cubic decay, improving the known quadratic one, is exactly what makes the inverse-gap second moments in the utility integral finite.
  • In the weaker metric E[‖M̂_k−M‖²_F − ‖M_k−M‖²_F], the paper gives an eigengap-free bound O~(√(kd))·√T, improving the previous unconditional bound by roughly √k.

Reading between the lines

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

  • My inference: the s³ gap decay is specific to β=2 eigenvalue repulsion; an analogous analysis in the symplectic setting (β=4, if the mechanism were modified accordingly) would give s⁵ decay and even better-behaved inverse-gap expectations, a testable extension the paper does not discuss.
  • My inference: if the real part of a complex Hermitian rank-k matrix can have rank up to 2k — for example, the real part of the rank-1 projector onto u=(1,i)/√2 is (1/2)I₂ — then the output of Algorithm 1 is not guaranteed to be a rank-k matrix as Theorem 2.2 states; the natural repair is an extra projection onto the nearest real rank-k matrix, whose additional error the current proof, as written,
  • My inference: the finiteness mechanism identified here, that β=2 repulsion renders E[1/(γ_i−γ_j)²] finite while β=1 leaves it divergent, indicates why real Gaussian noise cannot reach the stated utility bound by this route and suggests that any real-noise analogue needs a qualitatively different control on small gaps.
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

2 major / 3 minor

Summary. The paper proposes a complex variant of the Gaussian mechanism for differentially private rank-k covariance approximation. Its main theoretical tool is to view Gaussian noise addition as a matrix Brownian motion, so that the evolution of eigenvalues and eigenvectors is governed by Dyson Brownian motion. The claimed results are: Theorem 2.2, an (epsilon,delta)-DP algorithm outputting a real rank-k matrix Y with expected Frobenius error O~(sqrt(kd) sigma_k/(sigma_k - sigma_{k+1}) sqrt(log(1/delta))/epsilon); Theorem 2.3, an average-case bound on the change of the complex best rank-k approximation under complex Gaussian perturbations; and Theorem 2.4, improved high-probability lower bounds on eigenvalue gaps of GUE/GOE matrices with arbitrary initial matrix. Theorem 2.2 is derived from Theorem 2.3 in Section 6 by taking the real part of the complex rank-k approximation. The proofs of Theorems 2.3 and 2.4 are extensive and use stochastic calculus and density-based change-of-variables arguments.

Significance. If correct, Theorem 2.2 would improve the Analyze Gauss bound of Dwork et al. by a factor of about sqrt(k) under a k-th eigengap assumption, which is a meaningful result for private PCA and covariance approximation. The Dyson Brownian motion viewpoint is a conceptually interesting alternative to Davis-Kahan-type perturbation bounds, and Theorems 2.3 and 2.4 are independent contributions with falsifiable quantitative predictions: the s^3 gap probability for GUE improves the s^2 bound of Nguyen-Tao-Vu in the Gaussian special case. The derivations are analytic and do not rely on numerical fitting. However, the central transfer step from the complex Hermitian result to a real rank-k output is invalid, so the paper's headline private low-rank theorem is not established in its current form.

major comments (2)
  1. [Section 6, proof of Theorem 2.2] The proof asserts that Y = Real(V_hat Sigma_k_hat V_hat^*) is a matrix of rank at most k, and hence is the best real rank-k approximation of M_hat_k. This assertion is false. For u = (1,i)/sqrt(2), the rank-1 Hermitian matrix uu^* has real part (1/2)I_2, which has rank 2. More generally, the real part of a Hermitian rank-k matrix can have rank as large as 2k. Consequently, for k=1 and a generic complex Gaussian perturbation, the output of Algorithm 1 has rank 2 with probability 1. This is not a minor technicality: the theorem's promise that the algorithm 'outputs a rank-k matrix Y' is the defining property of a rank-k approximation mechanism, and the subsequent step 'Y in argmin_{Z in R_k} ||M_hat_k - Z||_F' relies directly on the false rank bound.
  2. [Section 6, inequality (37)] Even if Theorem 2.3 is accepted as a bound on ||M_hat_k - M_k||_F for the complex Hermitian projection M_hat_k, the transfer to a real output Y via ||Y - M_k||_F <= 2 ||M_hat_k - M_k||_F fails when Y is not a real rank-k matrix. The current Algorithm 1 does not project onto the real rank-k manifold, and no alternate output rule with a re-derived utility bound is provided. Thus the advertised utility guarantee of Theorem 2.2 is unproven for any real rank-k output. Repairing this would require changing the output rule and redoing the utility analysis, not a local correction.
minor comments (3)
  1. [Section 8.3, around Eq. (129)] The citation 'Lem. 8.3' in the completed proof should refer to Proposition 8.3; please correct the cross-reference.
  2. [Section 6, privacy paragraph] The privacy argument can be made valid by explicitly noting that the imaginary part i(W_2 - W_2^T) is fresh randomness independent of the data, so Algorithm 1 is a post-processing of the real Gaussian mechanism output with independent randomness; the current wording may confuse readers into thinking no fresh randomness is used.
  3. [Section 7 and Section 8] The proof of Theorem 2.3 uses Theorem 2.4 through Lemma 9.2 and Corollary 9.4 before the proof of Theorem 2.4 appears in Section 9; a forward pointer in Section 8 would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's bounds are derived from the stated Dyson Brownian motion SDEs and the explicit GUE density, not from fitted parameters or load-bearing self-citations; the reviewer-identified rank flaw is a correctness issue, not a circular reduction.

full rationale

The main result Theorem 2.3 is obtained by defining the Hermitian diffusion Φ(t)=M+B(t), using the standard Dyson SDEs (6)-(7) from [27]/[13]/[3], computing the Itô derivative of the rank-k process Ψ(t)=U(t)Λ(t)U(t)* (Lemmas 8.5 and 8.6), and bounding the resulting inverse-gap integrals with Theorem 2.4. Theorem 2.4 is proved from the GUE joint density (17) via the gap-comparison Lemma 4.2 and explicit change-of-variables maps g and φ (Propositions 9.8 through 9.16 and Lemmas 9.10, 9.12, 9.15, 9.16); no parameter is fitted to data and no target bound is assumed as an input. Lemma 9.2 invokes Theorem 2.4 as a forward reference for the 'bad event' used in the proof of Theorem 2.3, but Lemma 9.2 is not used in the proof of Theorem 2.4, so there is no circular dependency. The self-citations [59] and [60] are explicitly described as earlier conference versions of the present paper (footnote on page 1) and are provenance only; the proofs here are complete and self-contained, and no uniqueness or existence claim is imported from those earlier papers. The reviewer's counterexample to Section 6's assertion that Real(Vhat Σk Vhat*) has rank at most k is a false-premise correctness error in the proof of Theorem 2.2, not a circular definition, a fitted input renamed as a prediction, or a load-bearing self-citation, so it is outside the circularity score.

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

No fitted parameters appear; all quantities are universal constants or theorem assumptions. The proofs rest on standard Dyson Brownian motion facts, the GUE/GOE joint density, eigenvalue rigidity, and Davis-Kahan/Weyl perturbation inequalities. The rank flaw is not a missing axiom but an erroneous proof step in Section 6.

assumptions (7)
  • standard math Dyson Brownian motion SDEs (6)-(7) have unique strong solutions and paths do not collide for beta >= 1.
    Invoked in Lemma 3.2 and Lemma 3.4; needed for gap comparison, Itô manipulations, and continuity arguments.
  • standard math Eigenvalue joint density formula (17) for GUE/GOE with repulsion exponent beta.
    Used in Lemma 9.5 and Section 9.2 to integrate over small-gap sets.
  • standard math Rigidity of GUE/GOE eigenvalues (Lemma 9.7, from [30]).
    Used to localize eigenvalues in the bulk and edge cases of Lemma 9.5.
  • standard math Davis-Kahan sin-theta theorem and Weyl's inequality.
    Used for deterministic perturbation comparisons and for the worst-case gap bound in Proposition 8.3.
  • domain assumption Assumption 2.1: sigma_k - sigma_{k+1} >= 4 sqrt(T d).
    The utility bounds in Theorems 2.2 and 2.3 are conditional on this gap; Appendix A argues it is necessary for the stronger metric.
  • domain assumption sigma_1 <= d^50.
    This is a proof artifact controlling the bad event in Lemma 8.2; the authors note it can be replaced by sigma_1 <= d^C.
  • domain assumption Row-norm bounded sensitivity model for differential privacy.
    Defines neighboring matrices in Section 1 and fixes the Gaussian mechanism's noise scale.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations." pith.science (2026). https://pith.science/paper/NUO4U7DX

@misc{pith2026250207657,
  author       = {Pith},
  title        = {Pith review of: Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NUO4U7DX}},
  note         = {Machine review of arXiv:2502.07657}
}
abstract

We consider the problem of approximating a $d \times d$ covariance matrix $M$ with a rank-$k$ matrix under $(\varepsilon,\delta)$-differential privacy. We present and analyze a complex variant of the Gaussian mechanism and obtain upper bounds on the Frobenius norm of the difference between the matrix output by this mechanism and the best rank-$k$ approximation to $M$. Our analysis provides improvements over previous bounds, particularly when the spectrum of $M$ satisfies natural structural assumptions. The novel insight is to view the addition of Gaussian noise to a matrix as a continuous-time matrix Brownian motion. This viewpoint allows us to track the evolution of eigenvalues and eigenvectors of the matrix, which are governed by stochastic differential equations discovered by Dyson. These equations enable us to upper bound the Frobenius distance between the best rank-$k$ approximation of $M$ and that of a Gaussian perturbation of $M$ as an integral that involves inverse eigenvalue gaps of the stochastically evolving matrix, as opposed to a sum of perturbation bounds obtained via Davis-Kahan-type theorems. Subsequently, again using the Dyson Brownian motion viewpoint, we show that the eigenvalues of the matrix $M$ perturbed by Gaussian noise have large gaps with high probability. These results also contribute to the analysis of low-rank approximations under average-case perturbations, and to an understanding of eigenvalue gaps for random matrices, both of which may be of independent interest.

Figures

Figures reproduced from arXiv: 2502.07657 by the authors.

Figure 1
Figure 1. One run of a simulation of the eigenvalues [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. A diagram showing the structure of the proof of Theorems 2.3 and 2.2. Lower-level [PITH_FULL_IMAGE:figures/full_fig_p030_2.png] view at source ↗
Figure 3
Figure 3. A diagram of the proof of Theorem 2.4. Lemmas and Propositions below Lemma 9.5 [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

86 extracted references · 69 canonical work pages

  1. [1]

    Fast computation of low-rank matrix approxima- tions

    Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approxima- tions. Journal of the ACM (JACM), 54(2):9–es, 2007

    2007

  2. [2]

    Differen- tially private covariance estimation.Advances in Neural Information Processing Systems, 32, 2019

    Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Differen- tially private covariance estimation.Advances in Neural Information Processing Systems, 32, 2019

    2019

  3. [3]

    Number 118

    Greg W Anderson, Alice Guionnet, and Ofer Zeitouni.An introduction to random matrices. Number 118. Cambridge university press, 2010

    2010

  4. [4]

    Extreme gaps between eigenvalues of random matrices

    Gérard Ben Arous and Paul Bourgade. Extreme gaps between eigenvalues of random matrices. Annals of Probability, 41(4):2648–2681, 2013

    2013

  5. [5]

    Extreme gaps between eigenvalues of random matrices

    Gérard Ben Arous and Paul Bourgade. Extreme gaps between eigenvalues of random matrices. The Annals of Probability, 41(4):2648–2681, 2013

    2013

  6. [6]

    The Netflix Prize

    James Bennett and Stan Lanning. The Netflix Prize. InProceedings of KDD cup and workshop, volume 2007, page 35. New York, NY, USA., 2007

    2007

  7. [7]

    Matrix analysis, volume 169

    Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013

    2013

  8. [8]

    The Johnson-Lindenstrauss transform itself preserves differential privacy

    Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Lindenstrauss transform itself preserves differential privacy. In2012 IEEE 53rd Annual Symposium on Foun- dations of Computer Science, pages 410–419. IEEE, 2012

    work page 2012

Show all 86 references
  1. [9]

    Small gaps in the spectrum of the rectangular billiard

    Valentin Blomer, Jean Bourgain, Maksym Radziwiłł, and Zeev Rudnick. Small gaps in the spectrum of the rectangular billiard. InAnnales Scientifiques de l’Ecole Normale Superieure, volume 50, pages 1283–1300. Societe Mathematique de France, 2017

    2017

  2. [10]

    Practical privacy: the sulq framework

    Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. InProceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 128–138, 2005

    2005

  3. [11]

    Cambridge University Press, 2020

    Avrim Blum, John Hopcroft, and Ravindran Kannan.Foundations of data science. Cambridge University Press, 2020

    2020

  4. [12]

    Spectral fluctuations of classically chaotic quantum systems.Quantum Chaos and Statistical Nuclear Physics, 263:18–40, 1986

    Oriol Bohigas, Marie-Joya Giannoni, and Charles Schmit. Spectral fluctuations of classically chaotic quantum systems.Quantum Chaos and Statistical Nuclear Physics, 263:18–40, 1986

    1986

  5. [13]

    The eigenvector moment flow and local quantum unique ergod- icity

    Paul Bourgade and H-T Yau. The eigenvector moment flow and local quantum unique ergod- icity. Communications in Mathematical Physics, 350(1):231–278, 2017

    2017

  6. [14]

    Covariance-aware private mean estimation without private covariance estimation.Advances in neural information processing systems, 34:7950–7964, 2021

    Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance-aware private mean estimation without private covariance estimation.Advances in neural information processing systems, 34:7950–7964, 2021. 79

    2021

  7. [15]

    Gaps between zeros of the riemann zeta-function.The Quarterly Journal of Mathematics, 69(2):403–423, 2018

    HM Bui and MB Milinovich. Gaps between zeros of the riemann zeta-function.The Quarterly Journal of Mathematics, 69(2):403–423, 2018

    2018

  8. [16]

    Near-optimal differentially private principal components

    Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. Advances in neural information processing systems, 25:989–997, 2012

    2012

  9. [17]

    The lower tail of q-pushtasep.Communications in Mathemat- ical Physics, 405(3):64, 2024

    Ivan Corwin and Milind Hegde. The lower tail of q-pushtasep.Communications in Mathemat- ical Physics, 405(3):64, 2024

    2024

  10. [18]

    Chaos, complexity, and random matrices

    Jordan Cotler, Nicholas Hunter-Jones, Junyu Liu, and Beni Yoshida. Chaos, complexity, and random matrices. Journal of High Energy Physics, 2017(11):1–60, 2017

    2017

  11. [19]

    I: Theory

    Jane K Cullum and Ralph A Willoughby.Lanczos algorithms for large symmetric eigenvalue computations: Vol. I: Theory. SIAM, 2002

    2002

  12. [20]

    An overview of low-rank matrix recovery from incomplete observations

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

    2016

  13. [21]

    The rotation of eigenvectors by a perturbation

    Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1–46, 1970

    1970

  14. [22]

    Our data, ourselves: Privacy via distributed noise generation

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. InAnnual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486–503. Springer, 2006

    2006

  15. [23]

    Calibrating noise to sensi- tivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensi- tivity in private data analysis. InTheory of cryptography conference, pages 265–284. Springer, 2006

    2006

  16. [24]

    The algorithmic foundations of differential privacy.Founda- tions and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.Founda- tions and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014

    2014

  17. [25]

    Analyze Gauss: Optimal bounds for privacy-preserving principal component analysis

    Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze Gauss: Optimal bounds for privacy-preserving principal component analysis. InProceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 11–20, 2014

    2014

  18. [26]

    Random matrices and the statistical theory of energy levels IV

    FJ Dyson and M Lal Mehta. Random matrices and the statistical theory of energy levels IV. J. math. Phys, 4:701–12, 1963

    1963

  19. [27]

    A Brownian-motion model for the eigenvalues of a random matrix.Journal of Mathematical Physics, 3(6):1191–1198, 1962

    Freeman J Dyson. A Brownian-motion model for the eigenvalues of a random matrix.Journal of Mathematical Physics, 3(6):1191–1198, 1962

    1962

  20. [28]

    Statistical theory of the energy levels of complex systems

    Freeman J Dyson. Statistical theory of the energy levels of complex systems. i.Journal of Mathematical Physics, 3(1):140–156, 1962

    1962

  21. [29]

    Universality of random matrices and local relaxation flow.Inventiones mathematicae, 185(1):75–119, 2011

    László Erdős, Benjamin Schlein, and Horng-Tzer Yau. Universality of random matrices and local relaxation flow.Inventiones mathematicae, 185(1):75–119, 2011

    2011

  22. [30]

    Rigidity of eigenvalues of generalized Wigner matrices

    László Erdős, Horng-Tzer Yau, and Jun Yin. Rigidity of eigenvalues of generalized Wigner matrices. Advances in Mathematics, 229(3):1435–1515, 2012

    2012

  23. [31]

    Small gaps of goe

    Renjie Feng, Gang Tian, and Dongyi Wei. Small gaps of goe. Geometric and Functional Analysis, 29(6):1794–1827, 2019. 80

    2019

  24. [32]

    Large gaps of cue and gue.arXiv preprint arXiv:1807.02149, 2018

    Renjie Feng and Dongyi Wei. Large gaps of cue and gue.arXiv preprint arXiv:1807.02149, 2018

    2018 arXiv

  25. [33]

    Functional form for the leading correction to the distri- bution of the largest eigenvalue in the gue and lue.Journal of Mathematical Physics, 59(5), 2018

    Peter J Forrester and Allan K Trinh. Functional form for the leading correction to the distri- bution of the largest eigenvalue in the gue and lue.Journal of Mathematical Physics, 59(5), 2018

    2018

  26. [34]

    Ito calculus and complex brownian motion, January 2015

    Nic Freeman. Ito calculus and complex brownian motion, January 2015

    2015

  27. [35]

    Order estimation via matrix completion for multi-switch antenna selection.IEEE Signal Processing Letters, 28:2063–2067, 2021

    Vaibhav Garg, Alba Pages-Zamora, and Ignacio Santamaria. Order estimation via matrix completion for multi-switch antenna selection.IEEE Signal Processing Letters, 28:2063–2067, 2021

    2021

  28. [36]

    Statistical ensembles of complex, quaternion, and real matrices

    Jean Ginibre. Statistical ensembles of complex, quaternion, and real matrices. Journal of Mathematical Physics, 6(3):440–449, 1965

    1965

  29. [37]

    Probing symmetries of quantum many-body systems through gap ratio statistics.Physical Review X, 12(1):011006, 2022

    Olivier Giraud, Nicolas Macé, Éric Vernier, and Fabien Alet. Probing symmetries of quantum many-body systems through gap ratio statistics.Physical Review X, 12(1):011006, 2022

    2022

  30. [38]

    Circular law

    Vyacheslav L Girko. Circular law. Theory of Probability & Its Applications, 29(4):694–706, 1985

    1985

  31. [39]

    Smooth sensitivity based approach for differentially private PCA

    Alon Gonen and Ram Gilad-Bachrach. Smooth sensitivity based approach for differentially private PCA. InAlgorithmic Learning Theory, pages 438–450. PMLR, 2018

    2018

  32. [40]

    Random-matrix theories in quantum physics: common concepts.Physics Reports, 299(4-6):189–425, 1998

    Thomas Guhr, Axel Müller-Groeling, and Hans A Weidenmüller. Random-matrix theories in quantum physics: common concepts.Physics Reports, 299(4-6):189–425, 1998

    1998

  33. [41]

    Principalcomponent analysis andperturbation theory–based robust damage detection of multifunctional aircraft structure.Structural Health Monitoring, 12(3):263–277, 2013

    Rafik Hajryaand NazihMechbal. Principalcomponent analysis andperturbation theory–based robust damage detection of multifunctional aircraft structure.Structural Health Monitoring, 12(3):263–277, 2013

    2013

  34. [42]

    Estimating the intrinsic dimension of hyperspectral images using a noise-whitened eigengap approach

    Abderrahim Halimi, Paul Honeine, Malika Kharouf, Cédric Richard, and Jean-Yves Tourneret. Estimating the intrinsic dimension of hyperspectral images using a noise-whitened eigengap approach. IEEE Transactions on Geoscience and Remote Sensing, 54(7):3811–3821, 2016

    2016

  35. [43]

    Understanding alternating minimization for matrix completion

    Moritz Hardt. Understanding alternating minimization for matrix completion. In2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 651–660. IEEE, 2014

    2014

  36. [44]

    Beating randomized response on incoherent matrices

    Moritz Hardt and Aaron Roth. Beating randomized response on incoherent matrices. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1255– 1268, 2012

    2012

  37. [45]

    Beyond worst-case analysis in private singular vector com- putation

    Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector com- putation. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 331–340, 2013

    2013

  38. [46]

    Collision or non-collision problem for interacting Brownian particles.Pro- ceedings of the Japan Academy, Series A, Mathematical Sciences, 82(4):66–70, 2006

    Kiyokazu Inukai. Collision or non-collision problem for interacting Brownian particles.Pro- ceedings of the Japan Academy, Series A, Mathematical Sciences, 82(4):66–70, 2006

    2006

  39. [47]

    An introduction to statistical learning, volume 112

    Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning, volume 112. Springer, 2013. 81

    2013

  40. [48]

    Universality of the local spacing distribution in certain ensembles of hermitian wigner matrices

    Kurt Johansson. Universality of the local spacing distribution in certain ensembles of hermitian wigner matrices. Communications in Mathematical Physics, 215:683–705, 2001

    2001

  41. [49]

    Random matrices and determinantal processes

    Kurt Johansson. Random matrices and determinantal processes. arXiv preprint math- ph/0510038, 2005

    2005

  42. [50]

    Choosing a subset of principal components or variables.Principal component analysis, pages 111–149, 2002

    Ian T Jolliffe. Choosing a subset of principal components or variables.Principal component analysis, pages 111–149, 2002

    2002

  43. [51]

    On differentially private low rank approximation

    Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1395–1414. SIAM, 2013

    2013

  44. [52]

    springer, 1991

    Ioannis Karatzas and Steven Shreve.Brownian motion and stochastic calculus. springer, 1991

    1991

  45. [53]

    University of Cali- fornia, Berkeley, 2020

    Archit U Kulkarni.Random Matrix Theory in Numerical Linear Algebra. University of Cali- fornia, Berkeley, 2020

    2020

  46. [54]

    Singular subspace perturbation bounds via rectangular ran- dom matrix diffusions.arXiv preprint arXiv:2406.02502, 2024

    Peiyao Lai and Oren Mangoubi. Singular subspace perturbation bounds via rectangular ran- dom matrix diffusions.arXiv preprint arXiv:2406.02502, 2024

    2024 arXiv

  47. [55]

    Convergence of local statistics of Dyson Brownian motion

    Benjamin Landon and Horng-Tzer Yau. Convergence of local statistics of Dyson Brownian motion. Communications in Mathematical Physics, 355(3):949–1000, 2017

    2017

  48. [56]

    Stochastic calculus: An introduction with applications.American Mathe- matical Society, 2010

    Gregory F Lawler. Stochastic calculus: An introduction with applications.American Mathe- matical Society, 2010

    2010

  49. [57]

    A polynomial-time algorithm and applications for matrix sampling from Harish-Chandra–Itzykson-Zuber densities

    Jonathan Leake, Colin S McSwiggen, and Nisheeth K Vishnoi. A polynomial-time algorithm and applications for matrix sampling from Harish-Chandra–Itzykson-Zuber densities. InACM symposium on theory of computing STOC, 2021

    2021

  50. [58]

    Bulk universality for deformed Wigner matrices

    Ji Oon Lee, Kevin Schnelli, Ben Stetler, and Horng-Tzer Yau. Bulk universality for deformed Wigner matrices. The Annals of Probability, 44(3):2349–2425, 2016

    2016

  51. [59]

    Re-analyze Gauss: Bounds for private matrix approx- imation via Dyson Brownian motion

    Oren Mangoubi and Nisheeth Vishnoi. Re-analyze Gauss: Bounds for private matrix approx- imation via Dyson Brownian motion. InAdvances in Neural Information Processing Systems, volume 35, pages 38585–38599, 2022

    2022

  52. [60]

    Oren Mangoubi and Nisheeth K. Vishnoi. Private covariance approximation and eigenvalue- gap bounds for complex gaussian perturbations. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine L...

    2023

  53. [61]

    Pri- vate matrix approximation and geometry of unitary orbits

    Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, and Nisheeth K Vishnoi. Pri- vate matrix approximation and geometry of unitary orbits. InConference on Learning Theory, pages 3547–3588. PMLR, 2022

    2022

  54. [62]

    On the unreasonable effectiveness of single vector krylov methods for low-rank approximation

    Raphael Meyer, Cameron Musco, and Christopher Musco. On the unreasonable effectiveness of single vector krylov methods for low-rank approximation. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 811–845. SIAM, 2024

    2024

  55. [63]

    The pair correlation of zeros of the zeta function

    Hugh L Montgomery. The pair correlation of zeros of the zeta function. InProc. Symp. Pure Math, volume 24, pages 181–193, 1973. 82

    1973

  56. [64]

    Cambridge University Press, 2010

    Peter Mörters and Yuval Peres.Brownian motion, volume 30. Cambridge University Press, 2010

    2010

  57. [65]

    Random matrices: tail bounds for gaps between eigenvalues

    Hoi Nguyen, Terence Tao, and Van Vu. Random matrices: tail bounds for gaps between eigenvalues. Probability Theory and Related Fields, 167(3):777–816, 2017

    2017

  58. [66]

    Random perturbation of low rank matrices: Improving classical bounds

    Sean O’Rourke, Van Vu, and Ke Wang. Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra and its Applications, 540:26–59, 2018

    2018

  59. [67]

    Solving sparse linear systems faster than matrix multi- plication

    Richard Peng and Santosh Vempala. Solving sparse linear systems faster than matrix multi- plication. In Proceedings of the 2021 ACM-SIAM symposium on discrete algorithms (SODA), pages 504–521. SIAM, 2021

    2021

  60. [68]

    Eigenvalues and condition num- bers of complex random matrices

    Tharmalingam Ratnarajah, Rémi Vaillancourt, and M Alvo. Eigenvalues and condition num- bers of complex random matrices. SIAM Journal on Matrix Analysis and Applications, 26(2):441–456, 2004

    2004

  61. [69]

    On the calibration of sensor arrays for pattern recognition using the minimal number of experiments

    Irene Rodriguez-Lujan, Jordi Fonollosa, Alexander Vergara, Margie Homer, and Ramon Huerta. On the calibration of sensor arrays for pattern recognition using the minimal number of experiments. Chemometrics and Intelligent Laboratory Systems, 130:123–134, 2014

    2014

  62. [70]

    Interacting Brownian particles and the Wigner law.Prob- ability theory and related fields, 95(4):555–570, 1993

    Leonard CG Rogers and Zhan Shi. Interacting Brownian particles and the Wigner law.Prob- ability theory and related fields, 95(4):555–570, 1993

    1993

  63. [71]

    Zeros of principal l-functions and random matrix theory

    Zeév Rudnick, Peter Sarnak, et al. Zeros of principal l-functions and random matrix theory. Duke Mathematical Journal, 81(2):269–322, 1996

    1996

  64. [72]

    Old techniques in differentially private linear regression

    Or Sheffet. Old techniques in differentially private linear regression. InAlgorithmic Learning Theory, pages 789–827. PMLR, 2019

    2019

  65. [73]

    Topics in random matrix theory, volume 132

    Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012

    2012

  66. [74]

    The asymptotic distribution of a single eigenvalue gap of a Wigner matrix

    Terence Tao. The asymptotic distribution of a single eigenvalue gap of a Wigner matrix. Probability Theory and Related Fields, 157(1):81–106, 2013

    2013

  67. [75]

    The price of privacy for low-rank factorization.Advances in Neural Informa- tion Processing Systems, 31, 2018

    Jalaj Upadhyay. The price of privacy for low-rank factorization.Advances in Neural Informa- tion Processing Systems, 31, 2018

    2018

  68. [76]

    Random schrödinger operators on long boxes, noise explosion and the goe.Transactions of the American Mathematical Society, 366(7):3709–3728, 2014

    Benedek Valkó and Bálint Virág. Random schrödinger operators on long boxes, noise explosion and the goe.Transactions of the American Mathematical Society, 366(7):3709–3728, 2014

    2014

  69. [77]

    High-dimensional probability: An introduction with applications in data science, volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  70. [78]

    A tutorial on spectral clustering.Statistics and computing, 17:395–416, 2007

    Ulrike Von Luxburg. A tutorial on spectral clustering.Statistics and computing, 17:395–416, 2007

    2007

  71. [79]

    Perturbation bounds in connection with singular value decomposition.BIT Numerical Mathematics, 12:99–111, 1972

    Per-Åke Wedin. Perturbation bounds in connection with singular value decomposition.BIT Numerical Mathematics, 12:99–111, 1972

    1972

  72. [80]

    Characteristic vectors of bordered matrices with infinite dimensions.The Annals of Mathematics, 62(3):548, 1955

    Eugene P Wigner. Characteristic vectors of bordered matrices with infinite dimensions.The Annals of Mathematics, 62(3):548, 1955. 83

    1955

  73. [81]

    Gatlinberg conference on neutron physics.Oak Ridge National Laboratory Report, 1956

    Eugene P Wigner. Gatlinberg conference on neutron physics.Oak Ridge National Laboratory Report, 1956

    1956

  74. [82]

    A useful variant of the davis–kahan theorem for statisticians

    Yi Yu, Tengyao Wang, and Richard J Samworth. A useful variant of the davis–kahan theorem for statisticians. Biometrika, 102(2):315–323, 2015

    2015

  75. [83]

    A note on exploratory item factor analysis by singular value decomposition.Psychometrika, 85(2):358–372, 2020

    Haoran Zhang, Yunxiao Chen, and Xiaoou Li. A note on exploratory item factor analysis by singular value decomposition.Psychometrika, 85(2):358–372, 2020. 84 A Tightness of the upper bound in Theorem 2.3 In this section, we show that the upper bound in Theorem 2.3 is tight up t...

    2020

  76. [84]

    If we only wish to bound the weaker utility metric ∥ ˆMk−M∥2 F−∥Mk−M∥2 F, we can instead apply Ito’s Lemma to the function g(Y ) :=∥Y−M∥2 F

    Applying Ito’s lemma to the weaker Frobenius norm metric.When bounding the strongerutilitymetric ‖‖‖ˆMk−Mk ‖‖‖ 2 F intheproofofTheorem2.3weapplyIto’slemma(Lemma 3.1) to the function f(Y ) = ∥Y∥2 F. If we only wish to bound the weaker utility metric ∥ ˆMk−M∥2 F−∥Mk−M∥2 F, we ca...

  77. [85]

    To see why, we first note that from the proof of Theorem 2.3, we have dΨ(t) Eq

    Canceling the eigengap terms.The extra term−2Mij in the first derivative (305) leads to cancellations of the terms in the utility bound which depend on the eigenvalue gap. To see why, we first note that from the proof of Theorem 2.3, we have dΨ(t) Eq. (101) = d∑ i=1 λi(t)d(ui(...

  78. [86]

    classical

    Bounding the higher-order terms.More specifically, the higher-order terms are H(t) = d∑ i=1 ∑ j̸=i λi(t)−λj(t) (γi(t)−γj(t))2× d∑ ℓ=1 (γℓ(0)−γℓ(t))⟨uℓ(t)u∗ ℓ(t), ui(t)u∗ i (t)⟩ dt +2 d∑ i=1 ∑ j̸=i λi(t)−λj(t) (γi(t)−γj(t))2× d∑ ℓ=1 γℓ(0)⟨uℓ(0)u∗ ℓ(0)−uℓ(t)u∗ ℓ(t), ui(t)u∗ i (t...

Pith tools

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