A Correlation-Gap Bound for Nonlinear Gaussian PCA

Chenghua Liu; Minbo Gao; Zhengfeng Ji

A Correlation-Gap Bound for Nonlinear Gaussian PCA

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

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

Pith's one-line read The Karhunen–Loève basis is within 1+O(d^{-1/2}) of the optimal basis for adaptive top-d Gaussian energy retention.

desk verdict A genuine new result: the first 1+O(d^{-1/2}) retained-energy bound for the Mallat–Zeitouni conjecture, via a clean Schur–Horn + uniform-matroid correlation-gap argument; the proof checks out, and the main caveat is one imported constant. read the letter →

arxiv 2607.15035 v1 pith:OFIG5OUQ submitted 2026-07-16 cs.DS cs.ITmath.IT

Minbo Gao , Zhengfeng Ji , Chenghua Liu This is my paper · ORCID

classification cs.DScs.ITmath.IT MSC 60G1562H2505B3590C27

keywords Karhunen–LoèvebasisnonlinearPCAadaptivetop-dselectionGaussianorderstatisticsuniformmatroidcorrelationgapmajorization

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 proves a quantitative version of a 2011 conjecture about principal component analysis for Gaussian data. The conjecture asked whether the Karhunen–Loève basis—the eigenbasis of the covariance matrix—remains optimal when, after seeing a sample, one keeps only its d largest coordinates in that basis. The paper establishes that every orthonormal basis achieves at most 1+O(1/√d) times the expected retained energy of the KL basis, so the possible advantage of any rotation vanishes as d grows. The result is dimension-free, depending only on the number of retained coordinates, and it justifies the common pipeline of PCA followed by per-sample sparse thresholding with a near-optimality guarantee. A reader should care because this is the first near-one comparison for the retained-energy form of the problem, complementing earlier constant-factor reconstruction-error bounds.

What carries the argument

The proof rests on a threshold identity for the sum of the largest d positive numbers, Top_d(a)=inf_{τ≥0}(dτ+Σ_i(a_i−τ)_+), which converts a per-sample adaptive selection into a deterministic one-parameter relaxation. Schur–Horn majorization and Karamata's inequality then show this relaxation is maximized at the eigenvalue vector of the covariance. The remaining loss is identified, level by level, with the correlation gap of the rank-d uniform matroid: the factor by which E[min(d, |S|)] over independent Bernoulli sets can fall below min(d, Σ_i q_i). That gap is controlled by the balancedness constant c_{d,r} of a contention-resolution scheme, imported with a sharp uniform-matroid value.

What would settle it

Compute, for a fixed small d and r, the ratio OPT_d(Σ)/KL_d(Σ) over a family of Gaussian covariances by exhaustive or numerical search over rotations; if any ratio exceeds γ_d^{-1}, the theorem is false. More directly, verify the imported balancedness constant: enumerate all independent Bernoulli marginals on r elements and check whether E[min(d,N)] is always at least c_{d,r} min(d, Σ q_i); a counterexample would invalidate Lemma 5.

Watch

Extended reading notes

Core claim

The central claim, Theorem 2, is that for any centered Gaussian vector with covariance Σ and rank r, the best d-term retained energy over all orthonormal bases, OPT_d(Σ), satisfies KL_d(Σ) ≤ OPT_d(Σ) ≤ c_{d,r}^{-1} KL_d(Σ) ≤ γ_d^{-1} KL_d(Σ), where KL_d(Σ) is the retained energy in the Karhunen–Loève basis, c_{d,r} is the balancedness constant of the rank-d uniform matroid, and γ_d^{-1} = 1 + 1/√(2πd) + O(d^{-1}). When r ≤ d the comparison is exact equality with the trace. In words, no rotation of the eigenbasis can capture more than a 1+O(d^{-1/2}) fraction of the energy that the KL basis retains by keeping the largest d coordinates per sample.

Load-bearing premise

The main theorem hinges on a constant taken from prior work on matroid rounding being correct and monotone in the rank; if that constant were smaller than claimed, the dimension-free 1+O(d^{-1/2}) bound would collapse.

Editorial extensions

If this is right

As d grows, the worst-case penalty of using the KL basis instead of optimizing over all rotations shrinks like 1/√d; at d=1000 it is already about 1.3% (the paper's quantitative figure).
The guarantee is dimension-free: it does not depend on the ambient dimension p or the rank r, only on the number d of retained coordinates.
When r≤d, the result is exact: every basis retains all the energy, so OPT_d = KL_d = Tr(Σ).
The retained-energy comparison complements, but does not imply, a near-one reconstruction-error result, since multiplicative factors do not survive subtracting from Tr(Σ).
The proof isolates the gap as the uniform-matroid correlation gap, so improvements in that constant would directly sharpen the PCA bound.

Reading between the lines

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

Because the proof reduces the problem to the uniform-matroid correlation gap, any improved balancedness constant—or a proof of exactness for specific eigen-decays—would transfer immediately into a sharper basis-optimality guarantee.
The threshold relaxation may be loose for highly non-diagonal covariances; testing the gap numerically for structured spectra (e.g., power-law or spiked) could show the true constant is smaller than γ_d^{-1}.
A full resolution of the exact conjecture will need to account for the joint Gaussian dependence induced by rotation, which the marginal-variance relaxation discards; this paper's framework suggests a route via higher-order correlations.
The same correlation-gap machinery could be applied to other adaptive selection rules, such as top-k of absolute values or block selection, yielding analogous near-optimal basis guarantees.

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.

Desk Editor's Note

read the letter

Best quick take: this is a real theorem, not a restatement. For any centered Gaussian and any orthonormal basis, the top-d retained energy of the rotated basis is at most 1 + 1/sqrt(2πd) + O(d^{-1}) times the top-d Karhunen–Loève retained energy. That is the first near-one retained-energy comparison for the Mallat–Zeitouni conjecture. Litvak–Tikhomirov give a universal constant and work with reconstruction error, not this objective.

What the paper does well: the proof is short and almost self-contained. Lemma 3 is the elementary top-d threshold identity. Lemma 4 is the key analytic step — the threshold relaxation depends only on coordinate variances, Schur–Horn majorizes those variances by the covariance eigenvalues, and Karamata pushes the relaxation to the KL basis. Lemma 6 layers the KL retained energy into an integral over Bernoulli level sets and identifies the loss against the threshold relaxation as exactly the uniform-matroid correlation gap. I checked the integral identity in Lemma 6; the algebra is right. The direction of the correlation-gap inequality is the correct one, and the reduction from large ∑q_i to the matroid-polytope case by coupling is valid. No fitted parameters, no circularity.

Soft spots: the load-bearing external input is the Kashaev–Santiago balancedness constant c_{d,r} and the assertion that c_{d,r} ≥ γ_d for all r>d. This is imported as a black box, with no proof and only a pointer to their paper. If that inequality were wrong, the dimension-free 1+1/sqrt(2πd) factor would collapse. The claim is plausible and likely correct, but the authors should either state the exact Kashaev–Santiago theorem or give a short binomial-tail proof of c_{d,r} ≥ γ_d. This is a minor-to-moderate presentation gap, not a demonstrated flaw.

The paper is also honest about what it does not do: the exact constant-one conjecture remains open, and the limitation discussion says plainly that a full resolution will need ideas beyond the marginal-variance relaxation. That is the right assessment.

Who should read it: people working on nonlinear approximation, Gaussian order statistics, or matroid correlation gaps. It deserves a serious referee and, after the external constant is pinned down more explicitly, publication.

Referee Report

0 major / 3 minor

Summary. This paper proves a 1+O(d^{-1/2})-approximate version of the retained-energy form of the Mallat–Zeitouni conjecture for nonlinear Gaussian PCA. Specifically, for a centered Gaussian vector in R^p with covariance eigenvalues λ_1 ≥ ... ≥ λ_p and rank r, it shows that for every orthonormal basis V, the expected energy retained by the adaptive top-d rule is at most γ_d^{-1} times the corresponding expected energy in the Karhunen–Loève basis, where γ_d^{-1}=1+1/√(2πd)+O(d^{-1}). The proof proceeds through a deterministic threshold identity, a Schur–Horn/Karamata relaxation to the eigenvalue vector, a layer-cake decomposition into independent Bernoulli level sets, and a comparison via the uniform-matroid correlation gap using the Kashaev–Santiago contention-resolution constant. The constant-one conjecture remains open, but the asymptotic factor tends to 1.

Significance. If correct, the result is a substantial quantitative step beyond Litvak–Tikhomirov's universal-constant comparison: it gives the first dimension-free retained-energy bound whose multiplicative factor approaches 1, with an explicit and conceptually clean argument. The proof is genuinely elegant: it identifies the loss in the relaxation with a sharp uniform-matroid correlation gap, and it is essentially self-contained modulo standard majorization theory and a published contention-resolution theorem. The lemmas are stated precisely and the internal steps—threshold identity, Schur–Horn/Karamata relaxation, Bernoulli coupling, and layer-cake identification—are all valid. The only non-self-contained ingredient is the quoted Kashaev–Santiago constant, which is a standard, checkable external result and not a circular step.

minor comments (3)

[Section 3.3 / Proof of Theorem 2] The dimension-free passage relies on the assertion that c_{d,r} converges from above to γ_d as r→∞, cited only as 'the analysis of Kashaev and Santiago (2023)'. Since this is load-bearing for the γ_d^{-1} bound, please give the precise theorem number or equation in that reference, or include a short derivation. This is a local clarity issue, not a substantive gap.
[Theorem 2 and throughout] The binomial coefficient is written as C(r,d); please define this notation explicitly or use \binom{r}{d} for consistency with the surrounding mathematical text.
[Title page / author affiliations] Minor typographical issue: 'T e chnology' in the affiliation should be 'Technology'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof derives the bound from standard majorization, layer-cake identities, and an external matroid balancedness theorem; the target inequality is never assumed.

full rationale

The derivation chain is self-contained and non-circular. Lemma 3 proves an exact variational identity for Top_d(a), which is then used in Lemma 4 to bound every rotated basis by the deterministic relaxation U_d(λ). The step from a basis to U_d(λ) uses only Schur's theorem (diagonal of V^T Σ V is majorized by λ) and Karamata's inequality for the convex function h_τ. No optimality of the KL basis is assumed there; it is derived from the relaxation. Lemma 6 uses a layer-cake decomposition to rewrite KL_d(Σ) as an integral of min(d, N_t) over independent Bernoulli level sets, and then applies the uniform-matroid Bernoulli bound of Lemma 5. That bound is imported from the external publication Kashaev and Santiago (2023), not from the present authors: it is a published theorem with its own proof and no fitted parameters. The final theorem combines KL_d(Σ) ≤ OPT_d(Σ) (which is just feasibility of the KL basis), OPT_d(Σ) ≤ U_d(λ) (Lemma 4), and U_d(λ) ≤ c_{d,r}^{-1} KL_d(Σ) (Lemma 6), yielding the stated factor. Nowhere is the conclusion OPT_d(Σ) ≤ γ_d^{-1} KL_d(Σ) used as an input. The only external dependency is the quoted balancedness constant c_{d,r} and the inequality c_{d,r} ≥ γ_d, which is a checkable published claim rather than a self-referential or fitted assumption. If that constant were wrong the finite-rank bound would fail, but that is a correctness and reproducibility concern about a cited theorem, not circularity in the present derivation. No self-citation is load-bearing, no fitted parameter is relabeled as a prediction, and no renaming of a known result occurs. Honest non-finding: score 0.

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

No free parameters or invented entities: the proof uses standard majorization and integration theorems plus one external sharp constant from Kashaev–Santiago. The central claim is not assumed anywhere.

assumptions (6)

standard math Schur–Horn theorem: the diagonal of VᵀΣV is majorized by the eigenvalue vector λ.
Invoked in Lemma 4 to reduce an arbitrary orthonormal basis V to its variance vector µ and bound Σ hτ(µi) by Σ hτ(λi).
standard math Karamata's inequality for convex hτ(u) = E[(uZ²−τ)_+].
Applied in Lemma 4 after proving hτ is convex; the majorized vector has smaller convex sum.
standard math Kashaev–Santiago optimal c_{d,r}-balanced contention-resolution scheme for rank-d uniform matroids exists, with c_{d,r} = 1 − C(r,d)(d/r)^d(1−d/r)^{r+1−d}.
Black box used in Lemma 5; supplies the exact correlation-gap constant and the subsequent γ_d comparison.
standard math Layer-cake/Tonelli identity Topd(b) = ∫₀^∞ min(d, #{i : b_i > t}) dt for nonnegative b.
Used in Lemma 6 to express KL retained energy as an integral of Bernoulli tails.
standard math m(t) = Σ_{i=1}^r P(λ_i Z_i² > t) is continuous and non-increasing from r to 0, so τ* with m(τ*) = d exists.
Used in Lemma 6 to identify U_d(λ) = ∫₀^∞ min(d, m(t)) dt.
domain assumption The data model is a centered Gaussian vector with known covariance; KL-basis coordinates are independent standard Gaussians scaled by eigenvalues.
The entire Mallat–Zeitouni problem is stated for Gaussian X; the result is about this distribution, not arbitrary distributions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Correlation-Gap Bound for Nonlinear Gaussian PCA." pith.science (2026). https://pith.science/paper/OFIG5OUQ

@misc{pith2026260715035,
  author       = {Pith},
  title        = {Pith review of: A Correlation-Gap Bound for Nonlinear Gaussian PCA},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OFIG5OUQ}},
  note         = {Machine review of arXiv:2607.15035}
}

abstract

Principal component analysis (PCA) is optimal for the linear reconstruction of Gaussian data, a foundational property underlying its central role in algorithms and signal processing. Its nonlinear analogue, however, is notoriously subtle: in 2011, Mallat and Zeitouni conjectured that the Karhunen--Lo\`eve (KL) basis remains optimal even when the retained coordinates are chosen adaptively per sample, a property that would theoretically justify the ubiquitous pipeline of PCA followed by sparse thresholding. In this paper, we establish a $1+O(1/\sqrt{d})$-approximate version of the retained-energy form of the Mallat--Zeitouni conjecture, showing that the KL basis is within this factor of the optimal basis. This dimension-free comparison depends only on the number of retained coordinates and shows that the possible advantage of optimizing over all orthonormal bases vanishes as $d$ grows. It complements the universal-constant reconstruction-error comparison of Litvak and Tikhomirov (Ann. Appl. Probab., 2018), while providing a comparison naturally suited for algorithmic analysis. Our proof rests on a clean, conceptual reduction: we relax arbitrary rotations to a deterministic threshold bound via Schur--Horn majorization, and identify the remaining loss with the correlation gap of the rank-$d$ uniform matroid over Gaussian level sets.

Figures

Figures reproduced from arXiv: 2607.15035 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 6 canonical work pages

[10]

Proceedings of the IEEE 98, 937–947

Sparse recovery using sparse matrices. Proceedings of the IEEE 98, 937–947. doi:10.1109/JPROC.2010.2045092. Gilbert, A.C., Li, Y., Porat, E., Strauss, M.J.,

arXiv 2010
[13]

Positivity 16, 1–28

Uniform estimates for order statistics and Orlicz functions. Positivity 16, 1–28. doi:10.1007/s11117-010-0107-3. Halko, N., Martinsson, P .G., Tropp, J.A.,

work page doi:10.1007/s11117-010-0107-3
[21]

The Annals of Applied Probability 28, 2083–2104

Order statistics of vectors with dependent coordinates, and the Karhunen–Loève basis. The Annals of Applied Probability 28, 2083–2104. doi: 10.1214/ 17-AAP1321,arXiv:1609.02126. Mallat, S.,

arXiv
[22]

doi:10.48550/arXiv.1109.0489,arXiv:1109.0489

A conjecture concerning optimality of the Karhunen–Loève basis in nonlinear reconstruction. doi:10.48550/arXiv.1109.0489,arXiv:1109.0489. Mallat, S.G., Zhang, Z.,

arXiv doi:10.48550/arxiv.1109.0489
[27]

Applied and Computational Harmonic Analysis 26, 301–321

CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis 26, 301–321. doi: 10.1016/j.acha. 2008.07.002. Pearson, K.,

doi:10.1016/j.acha 2008
[28]

Foundations and Trends in Theoretical Computer Science 10, 1–157

Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science 10, 1–157. doi:10.1561/0400000060. Yan, Q.,

doi:10.1561/0400000060
[29]

Mechanism design via correlation gap, in: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM. pp. 710–719. doi: 10.1137/1. 9781611973082.56. 12

doi:10.1137/1
[1933]

Journal of Educational Psychology 24, 417–441, 498–520

Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology 24, 417–441, 498–520. Part I DOI: 10.1037/h0071325; Part II DOI: 10.1037/h0070888. Husi´ c, E., Koh, Z.K., Loho, G., Végh, L.A.,

doi:10.1037/h0071325

Show all 29 references

[1936]

Psychome- trika 1, 211–218

The approximation of one matrix by another of lower rank. Psychome- trika 1, 211–218. doi:10.1007/BF02288367. Gilbert, A.C., Indyk, P .,

doi
[1960]

The Quarterly Journal of Mathematics 11, 50–59

Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics 11, 50–59. doi:10.1093/qmath/11.1.50. Musco, C., Musco, C.,

doi
[1992]

IEEE Transactions on Information Theory 38, 719–746

Image compression through wavelet transform coding. IEEE Transactions on Information Theory 38, 719–746. doi:10.1109/18.119733. Dinev, A., Weinberg, S.M.,

doi
[1993]

IEEE Transactions on Signal Processing 41, 3397–3415

Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing 41, 3397–3415. doi:10.1109/78.258082. Martinsson, P .G., Tropp, J.A.,

doi
[1997]

volume 169 ofGraduate T exts in Mathematics

Matrix Analysis. volume 169 ofGraduate T exts in Mathematics. Springer, New York. doi:10.1007/978-1-4612-0653-8. Blumensath, T., Davies, M.E.,

doi
[2001]

SIAM Review 43, 129–159

Atomic decomposition by basis pursuit. SIAM Review 43, 129–159. doi:10.1137/S003614450037906X. 10 David, H.A., Nagaraja, H.N.,

doi
[2002]

Springer Series in Statistics

Principal Component Analysis. Springer Series in Statistics. 2 ed., Springer, New York. doi:10.1007/b98835. Kashaev, D., Santiago, R.,

doi
[2003]

Wiley Series in Probability and Statistics

Order Statistics. Wiley Series in Probability and Statistics. 3 ed., Wiley, Hoboken, NJ. doi:10.1002/0471722162. DeVore, R.A.,

doi
[2005]

Comptes Rendus Mathématique 340, 445–448

Minima of sequences of gaussian random variables. Comptes Rendus Mathématique 340, 445–448. doi:10.1016/j.crma.2005.02.003. Gordon, Y., Litvak, A.E., Schütt, C., Werner, E.,

2005 doi
[2009]

Applied and Computational Harmonic Analysis 27, 265–274

Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis 27, 265–274. doi:10.1016/j.acha.2009.04.002. Chekuri, C., Vondrák, J., Zenklusen, R.,

2009 doi
[2010]

Correlation robust stochastic optimization, in: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM. pp. 1087–1096. doi:10.1137/1.9781611973075.88,arXiv:0902.1792. Arora, S., Ge, R., Moitra, A.,

arXiv
[2011]

SIAM Review 53, 217–288

Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review 53, 217–288. doi:10.1137/090771806. Hotelling, H.,

doi
[2012]

SIAM Journal on Computing 41, 436–453

Approximate sparse recovery: Optimizing time and measurements. SIAM Journal on Computing 41, 436–453. doi:10.1137/100816705. Gordon, Y., Litvak, A.E., Schütt, C., Werner, E.,

doi
[2014]

SIAM Journal on Computing 43, 1831–1879

Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing 43, 1831–1879. doi:10.1137/110839655. Chen, S.S., Donoho, D.L., Saunders, M.A.,

doi
[2015]

Randomized block Krylov methods for stronger and faster approximate singular value decomposition, in: Advances in Neural Information Processing Systems, Curran Associates, Inc.. pp. 1396–1404. URL: https://proceedings.neurips.cc/paper/2015/hash/ 1efa39bcaec6f390014916069369453...

2015 arXiv
[2018]

(Eds.), Analytic Aspects of Convexity

Around the simplex mean width conjecture, in: Bianchi, G., Colesanti, A., Gronchi, P . (Eds.), Analytic Aspects of Convexity. Springer International Publishing, Cham. volume 25 ofSpringer INdAM Series, pp. 73–84. doi:10.1007/978-3-319-71834-7_5. Litvak, A.E., Tikhomirov, K.,

doi
[2020]

Acta Numerica 29, 403–572

Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica 29, 403–572. doi:10.1017/S0962492920000021. Mirsky, L.,

doi
[2023]

Theoretical Computer Science 940, 81–96

A simple optimal contention resolution scheme for uni- form matroids. Theoretical Computer Science 940, 81–96. doi: 10.1016/j.tcs.2022.10.042, arXiv:2105.11992. Kunisky, D.,

2022 arXiv
[2024]

(Ed.), 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany

Simple and optimal online contention resolution schemes for k-uniform matroids, in: Guruswami, V . (Ed.), 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany. pp. 39:1–39:23. URL: https:/...

2024 arXiv
[2025]

Mathematical Programming 210, 407–456

On the correlation gap of matroids. Mathematical Programming 210, 407–456. doi:10.1007/s10107-024-02116-w,arXiv:2209.09896. Jolliffe, I.T.,

arXiv
[2026]

doi:10.48550/arXiv.2605.02023,arXiv:2605.02023

A revision of Litvak’s conjecture on Gaussian minima and a volumetric zone conjecture. doi:10.48550/arXiv.2605.02023,arXiv:2605.02023. 11 Litvak, A.E.,

doi arXiv

Pith tools

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

[1] [10]

Proceedings of the IEEE 98, 937–947

Sparse recovery using sparse matrices. Proceedings of the IEEE 98, 937–947. doi:10.1109/JPROC.2010.2045092. Gilbert, A.C., Li, Y., Porat, E., Strauss, M.J.,

arXiv 2010

[2] [13]

Positivity 16, 1–28

Uniform estimates for order statistics and Orlicz functions. Positivity 16, 1–28. doi:10.1007/s11117-010-0107-3. Halko, N., Martinsson, P .G., Tropp, J.A.,

work page doi:10.1007/s11117-010-0107-3

[3] [21]

The Annals of Applied Probability 28, 2083–2104

Order statistics of vectors with dependent coordinates, and the Karhunen–Loève basis. The Annals of Applied Probability 28, 2083–2104. doi: 10.1214/ 17-AAP1321,arXiv:1609.02126. Mallat, S.,

arXiv

[4] [22]

doi:10.48550/arXiv.1109.0489,arXiv:1109.0489

A conjecture concerning optimality of the Karhunen–Loève basis in nonlinear reconstruction. doi:10.48550/arXiv.1109.0489,arXiv:1109.0489. Mallat, S.G., Zhang, Z.,

arXiv doi:10.48550/arxiv.1109.0489

[5] [27]

Applied and Computational Harmonic Analysis 26, 301–321

CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis 26, 301–321. doi: 10.1016/j.acha. 2008.07.002. Pearson, K.,

doi:10.1016/j.acha 2008

[6] [28]

Foundations and Trends in Theoretical Computer Science 10, 1–157

Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science 10, 1–157. doi:10.1561/0400000060. Yan, Q.,

doi:10.1561/0400000060

[7] [29]

Mechanism design via correlation gap, in: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM. pp. 710–719. doi: 10.1137/1. 9781611973082.56. 12

doi:10.1137/1

[8] [1933]

Journal of Educational Psychology 24, 417–441, 498–520

Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology 24, 417–441, 498–520. Part I DOI: 10.1037/h0071325; Part II DOI: 10.1037/h0070888. Husi´ c, E., Koh, Z.K., Loho, G., Végh, L.A.,

doi:10.1037/h0071325