SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

Ankit Pensia; Ilias Diakonikolas; Samuel B. Hopkins; Stefan Tiegel

REVIEW 2 major objections 5 minor 20 references

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

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

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

Pith's one-line read Sum-of-squares certificates bound the $\eta$-sparse singular values of random Gaussian matrices by $o(1)$ whenever $n \gg \eta^2d^{2+\epsilon}$, nearly matching computational lower bounds.

desk verdict A serious, dense paper that likely closes the long-standing sparse-SSV certification gap; the one load-bearing proof step (Claim 4.26) is cut off mid-sentence and must be completed before I would accept. read the letter →

arxiv 2412.21203 v1 pith:WHBH7ABB submitted 2024-12-30 cs.DS cs.LG

Ilias Diakonikolas , Samuel B. Hopkins , Ankit Pensia , Stefan Tiegel This is my paper · ORCID

classification cs.DScs.LG MSC 68W2060B2062F3568Q17

keywords sum-of-squarescertificatessparsesingularvaluesrandommatricesrobustcovarianceestimationmeansubspacedistortionlow-degreelowerboundsgraph

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 asks when a polynomial-time algorithm can certify that a random $d\times n$ Gaussian matrix has no unit vector supported on $\eta n$ coordinates with large image—equivalently, that its maximum $\eta$-sparse singular value is small. The paper establishes that nontrivial certificates exist whenever $n \gg \eta^2 d^{2+\epsilon}$ for any constant $\epsilon>0$, running in time $(nd)^{O(1/\epsilon)}$, and in quasipolynomial time whenever $n \gg \eta^2 d^2$. That fills the quadratic gap between the previous polynomial-time guarantees ($n \gg \eta d^2$ or $\eta \ll 1/\sqrt{d}$) and restricted-model lower bounds that point to $n \gg \eta^2 d^2$ as the real threshold. If correct, the result makes the sparse-singular-value certificate a near-optimal engine for robust covariance and mean estimation, subspace distortion certification, sparse PCA, and $2\to p$ norm certification.

What carries the argument

The engine is a decomposition of the Schatten-$p$ norm polynomial $\left\|\frac1n\sum_{i\le n} w_i x_i x_i^{\top}\right\|_p^p$ into graph polynomials $P_G(w,x)$, one for each partition of the $p$ indices into equality classes; each $P_G$ is a sum over injective labellings of a merged-cycle graph $G$ of products of $w$'s and inner products $\langle x_i,x_j\rangle$. Each $P_G$ is then split by an Efron-Stein decomposition into a top component $P_G^{=V}$ and lower-order components that are re-expressed as smaller graph polynomials and bounded recursively. The top component is written as a quadratic form $(w^{\otimes q})^\top A_Q w^{\otimes q}$ in a random matrix $A_Q$, and the proof shows the graph-matrix expansion of $A_Q$ consists of admissible graph matrices—graphs obtained by merging circle and diamond vertices of alternating cycle graphs—whose expected operator norm is controlled by a maximum vertex-capacitated flow bound. The flow bound, together with an imported graph-matrix spectral estimate, is what produces the $n \gg \eta^2 d^{2+\epsilon}$ exponent.

What would settle it

Trace the proof of the flow claim exactly at the truncated case "If $f(v) \ne 0$ a," compute the maximum vertex-capacitated flow for the smallest admissible graph in which a diamond part has nonzero flow through a vertex with neighbors on both sides, and check the claimed lower bound; one counterexample would falsify the flow lemma and with it the main $n \gg \eta^2 d^{2+\epsilon}$ theorem.

Watch

Extended reading notes

Core claim

The central claim is a new family of sum-of-squares certificates for the maximum $\eta$-sparse singular value of $M/\sqrt n$ when $M$ has independent standard Gaussian entries. For every $\epsilon>0$ the paper gives an $(nd)^{O(1/\epsilon)}$-time algorithm that certifies the bound is $o(1)$ whenever $n \gg \eta^2 d^{2+\epsilon}$ and $\eta\le o(1)$; taking $\epsilon = 1/\log d$ yields an $(nd)^{O(\log d)}$-time algorithm whenever $n \gg \eta^2 d^2$. Quantitatively, the certificate is roughly $\eta^{1/4} + (\eta^2 d^2/n)^{1/8}d^{O(1)}$, and the same guarantees transfer to centered jointly subgaussian entries. The paper further argues that the $n \gg \eta^2 d^2$ regime is nearly the best possible among statistical-query and low-degree polynomial tests, so the new algorithm almost closes the gap between achievable certificates and restricted-model lower bounds.

Load-bearing premise

The argument's linchpin is a combinatorial flow bound on the merged circle-and-diamond graphs: if that bound is too weak by a constant factor, the certified exponent degrades and the $n\gg\eta^2d^{2+\epsilon}$ guarantee collapses.

Editorial extensions

If this is right

Robust covariance estimation of an unknown Gaussian with constant relative-spectral-norm accuracy becomes possible with $n = \tilde{\Omega}(\eta^2 d^{2+2\epsilon} + d^{1+\epsilon})$ corrupted samples in $n^{O(1/\epsilon)}$ time, nearly matching the low-degree lower bound of $n \gg \eta^2 d^2$.
Robust covariance-aware mean estimation achieves Mahalanobis error $O(\sqrt{\eta})$ with the same near-quadratic sample complexity, giving the first evidence that the information-theoretic $O(d)$ sample bound is inaccessible to efficient algorithms.
Random $d$-dimensional subspaces of $\mathbb{R}^n$ can be certified to have distortion $\tilde{O}(d^{1/2+\epsilon}/n^{1/4})$ in polynomial time and $\tilde{O}(d^{1/2}/n^{1/4})$ in quasipolynomial time, improving the previous $\tilde{O}(d/\sqrt{n})$ or $\tilde{O}(d^{1/4})$ certificates.
Certification bounds for sparse PCA and for the $2\to p$ norm of a random matrix improve in the moderate-sparsity, moderate-sample regime, and the Gaussian certificates extend to subgaussian data.
The newly established low-degree and statistical-query lower bounds show the $\eta^2 d^2$ threshold is nearly tight: any polynomial-factor improvement over the algorithm's range would refute those restricted-model conjectures.

Reading between the lines

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

If the $\eta^2 d^2$ threshold is the true polynomial-time barrier, then robust mean and covariance estimation at mildly subconstant contamination $\eta = d^{-c}$ follow a clean dimension-squared law, and differentially private estimators derived from robust ones inherit the same bottleneck.
The Efron-Stein-then-spectral-certificate pattern looks like a transferable design principle: after grouping a high-degree polynomial by its index-equality pattern, subtracting conditional expectations removes low-rank 'bad' eigenvectors and leaves a matrix whose spectral norm is governed by flow in a merged graph; one could try the same decomposition for spiked covariance, tensor PCA, or planted
A direct testable extension is to run the certificate on finite-$n$ subgaussian designs: the paper's transfer theorems predict the same $n \gg \eta^2 d^{2+\epsilon}$ threshold with only logarithmic overhead, which an experimental comparison against the fourth-moment certificate could verify.

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

Bottom line: if the main theorem survives referee scrutiny, this closes the sparse singular value certification gap in a meaningful way. Theorem 1.5 quadratically improves on the prior polynomial-time certificates (Fact 1.3 needs n >> eta d^2, Fact 1.4 needs eta << 1/sqrt(d)) and covers regimes like eta = 1/sqrt(d) with n around d^1.5, which the paper correctly identifies as open. The applications to robust covariance/mean estimation and subspace distortion are concrete, with clean sample-complexity statements, and the proof architecture - Efron-Stein decomposition layered on graph matrices - is genuinely new as far as I can tell. The paper is also honest about the gap between its certificate bound and the true sparse singular value, and about the conditional nature of the lower bounds.

The real soft spot is Claim 4.26. The proof text literally cuts off at "If f(v) != 0 a" and then asserts f'(x_t) = f(v) in both scenarios. This is not cosmetic: Lemma 4.22 depends on it, and Lemma 4.18's n-exponent depends on Lemma 4.22. If the missing argument loses any constant factor in the flow bound, the certified exponent degrades and the main threshold n >> eta^2 d^{2+epsilon} could fail. The intended repair - route f(v) through each preserved edge from the super-diamond to L and R - is plausible, and I expect it goes through, but the manuscript as written cannot be checked at that step. A reviewer needs the missing case written out.

Two smaller issues. Fact 4.21, the AMP20 graph-matrix spectral bound, is imported without proof; it is an explicit citation to a standard tool, so I would call that minor. The abstract's parenthetical "that we establish" for SQ and low-degree lower bounds overstates what Section 7 proves: the low-degree bounds are established there, but the SQ bounds are inherited via the cited BBHLS21 connection. Minor, but worth fixing. No code or formal verification, so the combinatorial accounting is human-checked only.

Who it is for: researchers in sum-of-squares, random matrix theory, and algorithmic robust statistics. It deserves a serious referee. I would send it out with the clear instruction that Claim 4.26 be completed before acceptance. The central claim's shape almost certainly survives, but the paper is not finished until that paragraph is.

Referee Report

2 major / 5 minor

Summary. The paper studies the problem of certifying an upper bound on the maximum η-sparse singular value of a random Gaussian d×n matrix. The main result, Theorem 1.5 (formalized as Theorem 4.4), gives an (nd)^{O(1/ε)}-time Sum-of-Squares certifier proving that the maximum η-sparse singular value of a normalized Gaussian matrix is o(1) whenever n ≫ η²d^{2+ε}, for any constant ε>0, and a quasipolynomial-time version when n ≫ η²d². The proof expands the Schatten-p norm of the relevant matrix into graph polynomials, applies an Efron-Stein decomposition to isolate low-rank parts, then bounds the remaining pieces using spectral norm estimates for admissible graph matrices imported from the graph-matrix framework of [AMP20]. The flow lower bound on admissible circle- and diamond-merged graphs (Lemma 4.22 and Claim 4.26) is the key combinatorial step that produces the n-exponent in the main threshold. The paper then derives applications to robust covariance and covariance-aware mean estimation, subspace-distortion certification, planted sparse vectors, 2→p norms of random matrices, and sparse PCA, and it establishes low-degree lower bounds for several of these tasks.

Significance. If the proof is correct, Theorem 1.5 is a substantial algorithmic advance: it achieves polynomial-time nontrivial sparse-singular-value certification in the range n ≫ η²d^{2+ε}, whereas previous polynomial-time certificates required n ≫ ηd² or η ≪ 1/√d. This nearly matches the low-degree and SQ lower bounds cited in the paper, and the downstream applications—notably robust covariance and mean estimation with near-optimal sample-versus-contamination tradeoffs, and subspace-distortion certificates of about d^{1/2+ε}/n^{1/4}—are concrete and important. The proposed connection between Efron-Stein decompositions and graph-matrix spectral bounds is creative and potentially reusable. The paper is also honest about its reliance on external results ([AMP20, Cor. 8.16]) and on restricted lower-bound models. However, the verification burden is high because the main theorem depends on a long chain of combinatorial lemmas, and one load-bearing step (Claim 4.26) is incomplete in the submitted text.

major comments (2)

[4.4.1 (Claim 4.26)] The proof of Claim 4.26 is incomplete at the point where the construction must route a positive flow through a merged super-diamond. After treating the case f(v)=0, the text reads 'If f(v) ≠ 0 a' and then stops; the next paragraph simply asserts that 'in each of the two scenarios above we have f'(x_t)=f(v)'. The omitted case, where the minimum vertex flow in a preserved equivalence class is positive, is exactly where the proof must show that f(v) units can be routed through the super-diamond without violating capacity constraints at neighboring super-circles. Since Claim 4.26 feeds directly into Lemma 4.22, which in turn supports Lemma 4.18 and ultimately Theorem 4.1 and Theorem 1.5, the central threshold n ≫ η²d^{2+ε} is not verifiable from the submitted text. The intended repair is plausible—route f(v) units along preserved edges from the super-diamond to L and R—but the full argument, including the capacity bookkeeping, must be written out.
[4.4 (Fact 4.21)] Fact 4.21 is stated as an adaptation of Corollary 8.16 of [AMP20] to an in-expectation bound with an explicit dependence on isolated vertices, but the adaptation is not proved or even sketched. The n-exponent in the final bound of Lemma 4.18 is exactly n^{(w(V)-w(Smin)+w(Viso))/2}, so any hidden constant or missing factor in this imported statement propagates into the threshold of Theorem 1.5. This is not circular because the certificate bound is derived from external concentration facts rather than fitted to the true value, but the manuscript should either prove the adaptation or provide a precise derivation with the parameter choices (for example, q ≈ w(Smin) log n) that justify dropping logarithmic factors.

minor comments (5)

[4.4.1] The derivation of Lemma 4.22 from Claims 4.23 and 4.26 is not written out; adding the short algebra (Claim 4.26 plus Claim 4.23 gives the extra -(3/2)(p-|S|) term) would improve readability.
[1.1 vs 4.4] The orientation of the matrix M switches between M ∈ R^{d×n} in Theorem 1.5 and M ∈ R^{n×d} with rows M_i in Theorem 4.4; the paper should state the convention once and use it consistently.
[2] In the squared-inner-product example, the sentence 'Using that E⟨Xi, Xj⟩² = d, we gt' contains a typo ('gt' should be 'get').
[1.2.2] Theorem 1.13 contains the typo 'distorition' in the statement; it should be 'distortion'.
[4.5] In the proof of Lemma 4.14, the notation 'P ⊆f(S) G′(M )' appears where 'P ⊆S G′(M )' is intended; the stray subscript should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SSV certificate is derived from independent concentration, graph-matrix, and flow arguments; self-citations are not load-bearing.

full rationale

The paper's central derivation chain is self-contained rather than circular. Theorem 4.1 is obtained from Lemma 4.8, whose proof combines an induction on graph polynomials with the spectral norm bound for admissible graph matrices (Lemma 4.18). Lemma 4.18 rests on Fact 4.21, an external adaptation of a graph-matrix norm bound from [AMP20], and on the combinatorial flow lower bound Lemma 4.22, proved through Claims 4.23--4.26. None of these steps defines the target quantity in terms of itself, and no parameter is fitted to the true sparse singular value: the certificate bound R_sos in Eq. (7) is the quantity being certified, not a fit to data. The reductions to robust statistics, subspace distortion, and 2-to-p norms use standard prior reductions ([KSS18], [MW21], [DHPT24]) with proofs included, so the applications are consequences of the certificate rather than restatements of its inputs. The paper does cite the authors' prior work, notably [DHPT24] for the Gaussian-to-subgaussian transfer, but Section 5 actually reproduces the comparison argument (Theorem 5.1) rather than merely invoking the citation, so the self-citation is not load-bearing. The only notable incompleteness is in Claim 4.26 at Section 4.4.1, where the proof text reads "If f(v)≠ 0 a" and then breaks off; this is a missing case in a flow-routing argument and is a correctness/verifiability gap, not a circular step. A failure of that flow bound would degrade the n-exponent, but that would be a false theorem, not a circular derivation. Overall, the derivation is independent of its conclusions.

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

The central claim rests on standard probability (Wick, Hermite, Gaussian concentration), the imported AMP20 graph-matrix norm bound, the authors' own earlier [DHPT24] transfer theorem, and the [KSS18] resilience reduction. No new physical entities are postulated. The admissible graph matrices, super-circle and super-diamond graphs, and graph polynomial decompositions are mathematical constructions internal to the proofs, not entities posited to make the result true without evidence. Free parameters are limited to the explicit algorithm knob p = Θ(1/ε) and the lower-bound construction constant δ = √η/1000; neither is fitted to data, and neither encodes the target result.

free parameters (2)

SoS degree p (equivalently 1/ε) = p = Θ(1/ε); ε = 1/log(d) for the quasi-polynomial time case
Algorithm knob balancing runtime (nd)^O(p) against the certified-bound slack d^(5/(2p)); explicitly stated in Theorem 1.5 and visible in R_sos (Eq. 7). Not fitted to data.
Hidden-direction offset δ in the lower-bound construction = δ = √η/1000
Chosen by hand in Lemma 7.10 and Lemma 7.11 so the contamination distribution A matches the first three Gaussian moments; a construction parameter of the hardness instance, not a fitted constant of the main theorem.

assumptions (9)

standard math Wick's theorem for Gaussian moments (Theorem 3.8) and its norm-weighted corollary (Corollary 3.9)
Used throughout Section 4 to evaluate Gaussian expectations, including the Efron-Stein peeling in Lemma 4.14 (step (18)).
standard math Hermite polynomial facts (Fact 3.10, properties H.1 through H.4) and the moment-matching criterion (Fact 3.11)
Used for the Hermite expansion of graph matrix entries (Observation 4.19) and for the lower-bound construction in Section 7.3.
standard math Graph-matrix spectral norm bound (Fact 4.21, adapted from [AMP20, Cor. 8.16])
Load-bearing: converts combinatorial flow bounds into spectral norm bounds for admissible graph matrices. Imported as a black box, not proved in the paper.
domain assumption Gaussian-to-subgaussian transfer theorem of [DHPT24] (Theorem 5.1 and the surrounding methodology)
Used in Section 5 to extend the certificates from Gaussian to jointly subgaussian entries. A prior result by the same author group, parameter-free with stated assumptions; the paper explicitly says 'All of the ideas in the present section are already present in [DHPT24]'.
standard math SoS/pseudo-expectation duality and algorithmic facts (Facts 3.2 through 3.7)
Standard SoS machinery cited to [Par00; Las01; BS14; JH16; RW17; Lau09]; Fact 3.7 is proved in the paper via strict feasibility of the uniform pseudo-expectation.
domain assumption Resilience-to-covariance-estimation reduction of [KSS18] (Lemma 6.4)
Load-bearing for Theorems 6.1 and 6.5; the paper repeats the argument but attributes the connection to [KSS18]: 'Theorem 6.1 follows from a known connection between certifying resilience and covariance estimation [KSS18].'
domain assumption Stability implies robust mean estimation (Facts 6.7 through 6.9, cited to [DK23; DKKLMS19])
Used in the covariance-aware mean estimation pipeline (Algorithm 6.10); imported from prior work.
standard math Well-spread subspaces have low distortion ([GLR10, Lemma 2.11]) and standard Gaussian concentration for ‖XᵀX − nI‖
Used in the soundness and completeness proofs of the subspace distortion algorithm (Theorem 6.12).
domain assumption Low-degree conjecture as a computational hardness oracle (Section 7.1)
The near-optimality claims ('nearly matched by ... lower bounds') are conditional on the low-degree and SQ conjectures; the paper states this explicitly in Section 7 and in the introduction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More." pith.science (2026). https://pith.science/paper/WHBH7ABB

@misc{pith2026241221203,
  author       = {Pith},
  title        = {Pith review of: SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WHBH7ABB}},
  note         = {Machine review of arXiv:2412.21203}
}

abstract

We study $\textit{sparse singular value certificates}$ for random rectangular matrices. If $M$ is an $n \times d$ matrix with independent Gaussian entries, we give a new family of polynomial-time algorithms which can certify upper bounds on the maximum of $\|M u\|$, where $u$ is a unit vector with at most $\eta n$ nonzero entries for a given $\eta \in (0,1)$. This basic algorithmic primitive lies at the heart of a wide range of problems across algorithmic statistics and theoretical computer science. Our algorithms certify a bound which is asymptotically smaller than the naive one, given by the maximum singular value of $M$, for nearly the widest-possible range of $n,d,$ and $\eta$. Efficiently certifying such a bound for a range of $n,d$ and $\eta$ which is larger by any polynomial factor than what is achieved by our algorithm would violate lower bounds in the SQ and low-degree polynomials models. Our certification algorithm makes essential use of the Sum-of-Squares hierarchy. To prove the correctness of our algorithm, we develop a new combinatorial connection between the graph matrix approach to analyze random matrices with dependent entries, and the Efron-Stein decomposition of functions of independent random variables. As applications of our certification algorithm, we obtain new efficient algorithms for a wide range of well-studied algorithmic tasks. In algorithmic robust statistics, we obtain new algorithms for robust mean and covariance estimation with tradeoffs between breakdown point and sample complexity, which are nearly matched by SQ and low-degree polynomial lower bounds (that we establish). We also obtain new polynomial-time guarantees for certification of $\ell_1/\ell_2$ distortion of random subspaces of $\mathbb{R}^n$ (also with nearly matching lower bounds), sparse principal component analysis, and certification of the $2\rightarrow p$ norm of a random matrix.

Figures

Figures reproduced from arXiv: 2412.21203 by the authors.

**Figure 1.** Minimum value of n d 2 as a function of η for polynomial-time η-SSV refutation algorithms. Note the discontinuity in the state of the art guarantees preceding our work. 1.1 Main Algorithmic Result: Sparse Singular Value Certificates In what follows, M is a d × n matrix with independent standard Gaussian entries. We always consider n ≥ d and n ≤ d O(1). With high probability, the maximum singular value of M satisfies… view at source ↗

**Figure 2.** Illustration of vertex merging process. Breaking the Schatten-p norm into graph polynomials. With this in place, we start by expanding out the Schatten-p norm. In particular, let Q be the set of all partitions of [p], and for any Q ∈ Q, we say that (i1, . . . , ip) ∈ [n] p respects Q if ij = ik if and only if j and k are in the same part of Q. Using the convention that ip+1 = i1 it follows that [PITH_FULL_IMAGE:fig… view at source ↗

**Figure 3.** Example of a sequence of circle and diamond merges a [PITH_FULL_IMAGE:figures/full_fig_p034_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: An illustration of Lemma 4.30. We can now prove Lemma 4.14. Lemma (Restatement of Lemma 4.14). Let p ∈ N and let G = (V, E) ∈ Gmerged_disjoint_cycles p,r , i.e., a vertex merge of a union of r cycles whose lengths sum to p. Let S ( V be a strict subset of the vertices …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 15 canonical work pages

[1]

Graph matr ices: norm bounds and applications

[AMP20] K. Ahn, D. Medarametla, and A. Potechin. “Graph matr ices: norm bounds and applications”. In: arXiv preprint arXiv:1604.03423 (2020). 75 [AUZ23] H. Asi, J. R. Ullman, and L. Zakynthinou. “From Robus tness to Privacy and Back”. In: Proc. 40th International Conference on Machine Learning (I CML)

arXiv 2020
[15]

A remark on compressed sensing

[KT07] B. S. Kashin and V. N Temlyakov. “A remark on compressed sensing”. In: Mathe- matical notes (2007). [KWB19] D. Kunisky, A. S. Wein, and A. S. Bandeira. “Notes on Com putational Hardness of Hypothesis Testing: Predictions Using the Low-Degree Li kelihood Ratio”. In: Mathematical Analysis, its Applications and Computation

work page 2007
[16]

New positive semideﬁnite relaxatio ns for nonconvex quadratic pro- grams

[Las01] J. B. Lasserre. “New positive semideﬁnite relaxatio ns for nonconvex quadratic pro- grams”. In: Advances in Convex Analysis and Global Optimization: Honor ing the Memory of C. Caratheodory (1873–1950) (2001). [Lau09] Monique Laurent. “Sums of squares, moment matrices and optimization over poly- nomials”. In: Emerging applications of algebraic geom...

work page 2001
[18]

Optimization of polynomial functions

[M03] Murray M. “Optimization of polynomial functions”. In : Canadian Mathematical Bul- letin (2003). [MW21] C. Mao and A. S. Wein. “Optimal spectral recovery of a p lanted vector in a sub- space”. In: arXiv preprint arXiv:2105.15081 (2021). [Nar22] S. Narayanan. “Private high-dimensional hypothes is testing”. In: Conference on Learning Theory. PMLR. 2022...

arXiv 2003
[19]

On the bit complexity of s um-of-squares proofs

[R W17] P. Raghavendra and B. Weitz. “On the bit complexity of s um-of-squares proofs”. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

work page 2017
[20]

Sparse princi pal component analysis

[ZHT06] H. Zou, T. Hastie, and R. Tibshirani. “Sparse princi pal component analysis”. In: Journal of computational and graphical statistics 15.2 (2006). [ZSWB22] I. Zadik, M. J. Song, A. S. Wein, and J. Bruna. “Lattice -based methods surpass sum-of-squares in clustering”. In: Proc. 35th Annual Conference on Learning Theory (COLT)

work page 2006
[270]

The dimension of almost spheric al sections of convex bodies

[Lin77] J. Lindenstrauss. “The dimension of almost spheric al sections of convex bodies”. In: Séminaire Maurey-Schwartz (1977), pp. 1–13. [LR V16] K. A. Lai, A. B. Rao, and S. Vempala. “Agnostic Estimat ion of Mean and Co- variance”. In: Proc. 57th IEEE Symposium on Foundations of Computer Scienc e (FOCS)

work page 1977
[2009]

Information-theore tically optimal sparse PCA

[DM14] Y. Deshpande and A. Montanari. “Information-theore tically optimal sparse PCA”. In: Proc. 2014 IEEE International Symposium on Information The ory

work page 2014

Show all 20 references

[2012]

Sum-of-squares proofs and the q uest toward optimal algorithms

[BS14] B. Barak and D. Steurer. “Sum-of-squares proofs and the q uest toward optimal algorithms”. In: arXiv preprint arXiv:1404.5236 (2014). [BS16] B. Barak and D. Steurer. “Proofs, beliefs, and algorithm s through the lens of sum- of-squares”. In: (2016). Course notes: https:...

2014 arXiv
[2014]

Sparse PCA via covari ance thresholding

[DM16] Y. Deshpande and A. Montanari. “Sparse PCA via covari ance thresholding”. In: Journal of Machine Learning Research (2016). [Don06] D. L Donoho. “Compressed sensing”. In: IEEE Transactions on information theory (2006). [ES81] B. Efron and C. Stein. “The jackknife estimat...

2016
[2015]

Noisy tensor completion via the s um-of-squares hierarchy

[BM16] B. Barak and A. Moitra. “Noisy tensor completion via the s um-of-squares hierarchy”. In: Conference on Learning Theory . 2016, pp. 417–445. [BPT12] G. Blekherman, P. A. Parrilo, and R. R. Thomas. Semideﬁnite Optimization and Convex Algebraic Geometry

2016
[2016]

Decoding by linear programmi ng

76 [CT05] E. J. Candes and T. Tao. “Decoding by linear programmi ng”. In: IEEE transactions on information theory (2005). [dBE08] A. d’Aspremont, F. Bach, and L. El Ghaoui. “Optimal Sol utions for Sparse Principal Component Analysis.” In: Journal of Machine Learning Research (...

2005 arXiv
[2017]

Ro- bust Estimators in High-Dimensions Without the Computatio nal Intractability

[DKKLMS19] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. M oitra, and A. Stewart. “Ro- bust Estimators in High-Dimensions Without the Computatio nal Intractability”. In: SIAM J. Comput. (2019). [DKKPP22] I. Diakonikolas, D. M. Kane, S. Karmalkar, A. Pens ia, and T. Pittas....

2019
[2018]

Tensor princip al component analysis via sum-of-square proofs

[HSS15] S. B. Hopkins, J. Shi, and D. Steurer. “Tensor princip al component analysis via sum-of-square proofs”. In: Conference on Learning Theory . 2015, pp. 956–1006. [HSSS16] S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. “Fa st spectral algorithms from sum-of-squares pr...

2015
[2019]

Subexp onential-time algorithms for sparse PCA

77 [DKWB24] Y. Ding, D. Kunisky, A. Wein, and A. Bandeira. “Subexp onential-time algorithms for sparse PCA”. In: Foundations of Computational Mathematics (2024). [DL09] C. Dwork and J. Lei. “Diﬀerential privacy and robust s tatistics”. In: Proc. 41st Annual ACM Symposium on Th...

2024
[2020]

Stable distributions, pseudorandom gen erators, embeddings, and data stream computation

78 [Ind06] P. Indyk. “Stable distributions, pseudorandom gen erators, embeddings, and data stream computation”. In: Journal of the ACM (JACM) (2006). [JH16] C. Josz and D. Henrion. “Strong duality in Lasserre’s hierarchy for polynomial optimization”. In: Optimization Letters (...

2006 arXiv
[2021]

Estimates of the Hermite and the Freud polynomials

[BC90] S. S. Bonan and D. S. Clark. “Estimates of the Hermite and the Freud polynomials”. In: Journal of Approximation Theory 63.2 (1990), pp. 210–224. [BGSUZ21] G. Brown, M. Gaboardi, A. D. Smith, J. R. Ullman, and L . Zakynthinou. “Covariance- Aware Private Mean Estimation W...

1990
[2022]

Robust covariance and sc atter matrix estimation under Huber’s contamination model

[CGR18] M. Chen, C. Gao, and Z. Ren. “Robust covariance and sc atter matrix estimation under Huber’s contamination model”. In: The Annals of Statistics (2018). [CHLLN23] C. L. Canonne, S. B. Hopkins, J. Li, A. Liu, and S. Nar ayanan. “The Full Landscape of Robust Mean Testing:...

2018
[2023]

High-dimensional a nalysis of semideﬁnite re- laxations for sparse principal components

[A W08] A. A. Amini and M. J. Wainwright. “High-dimensional a nalysis of semideﬁnite re- laxations for sparse principal components”. In: Proc. 2008 IEEE International Sym- posium on Information Theory

2008
[2024]

Almost Euc lidean subspaces of ℓN 1 via expander codes

[GLR10] V. Guruswami, J. R. Lee, and A. Razborov. “Almost Euc lidean subspaces of ℓN 1 via expander codes”. In: Combinatorica 30.1 (2010), pp. 47–68. [GL W08] V. Guruswami, J. Lee, and A. Wigderson. “Euclidean S ections of ℓN 1 with Sublinear Randomness and Error-Correction ov...

2010

Pith tools

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

[1] [1]

Graph matr ices: norm bounds and applications

[AMP20] K. Ahn, D. Medarametla, and A. Potechin. “Graph matr ices: norm bounds and applications”. In: arXiv preprint arXiv:1604.03423 (2020). 75 [AUZ23] H. Asi, J. R. Ullman, and L. Zakynthinou. “From Robus tness to Privacy and Back”. In: Proc. 40th International Conference on Machine Learning (I CML)

arXiv 2020

[2] [15]

A remark on compressed sensing

[KT07] B. S. Kashin and V. N Temlyakov. “A remark on compressed sensing”. In: Mathe- matical notes (2007). [KWB19] D. Kunisky, A. S. Wein, and A. S. Bandeira. “Notes on Com putational Hardness of Hypothesis Testing: Predictions Using the Low-Degree Li kelihood Ratio”. In: Mathematical Analysis, its Applications and Computation

work page 2007

[3] [16]

New positive semideﬁnite relaxatio ns for nonconvex quadratic pro- grams

[Las01] J. B. Lasserre. “New positive semideﬁnite relaxatio ns for nonconvex quadratic pro- grams”. In: Advances in Convex Analysis and Global Optimization: Honor ing the Memory of C. Caratheodory (1873–1950) (2001). [Lau09] Monique Laurent. “Sums of squares, moment matrices and optimization over poly- nomials”. In: Emerging applications of algebraic geom...

work page 2001

[4] [18]

Optimization of polynomial functions

[M03] Murray M. “Optimization of polynomial functions”. In : Canadian Mathematical Bul- letin (2003). [MW21] C. Mao and A. S. Wein. “Optimal spectral recovery of a p lanted vector in a sub- space”. In: arXiv preprint arXiv:2105.15081 (2021). [Nar22] S. Narayanan. “Private high-dimensional hypothes is testing”. In: Conference on Learning Theory. PMLR. 2022...

arXiv 2003

[5] [19]

On the bit complexity of s um-of-squares proofs

[R W17] P. Raghavendra and B. Weitz. “On the bit complexity of s um-of-squares proofs”. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

work page 2017

[6] [20]

Sparse princi pal component analysis

[ZHT06] H. Zou, T. Hastie, and R. Tibshirani. “Sparse princi pal component analysis”. In: Journal of computational and graphical statistics 15.2 (2006). [ZSWB22] I. Zadik, M. J. Song, A. S. Wein, and J. Bruna. “Lattice -based methods surpass sum-of-squares in clustering”. In: Proc. 35th Annual Conference on Learning Theory (COLT)

work page 2006

[7] [270]

The dimension of almost spheric al sections of convex bodies

[Lin77] J. Lindenstrauss. “The dimension of almost spheric al sections of convex bodies”. In: Séminaire Maurey-Schwartz (1977), pp. 1–13. [LR V16] K. A. Lai, A. B. Rao, and S. Vempala. “Agnostic Estimat ion of Mean and Co- variance”. In: Proc. 57th IEEE Symposium on Foundations of Computer Scienc e (FOCS)

work page 1977

[8] [2009]

Information-theore tically optimal sparse PCA

[DM14] Y. Deshpande and A. Montanari. “Information-theore tically optimal sparse PCA”. In: Proc. 2014 IEEE International Symposium on Information The ory

work page 2014