PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Algorithms for Sparse PCA and Robust Sparse Estimation

Giannis Iakovidis, Ankit Pensia

arXiv:2609.09701v1cs.DS

TL;DR

Sparse-PCA certification has a substantial computational bottleneck: standard SDP solvers require Ω(d^4) time. This paper relaxes the witness form to obtain fast certificates, including quadratic-time guarantees in a broad sparsity regime. It also applies the routines to robust sparse estimation, while the certificate's vector branch can require increased sparsity.

  • Problem

    The standard SDP provides sparse-PCA certificates, but existing general-purpose solvers require Ω(d^4) time.

    Source: §1.1 · p. 3

  • Method

    The algorithm relaxes the witness to allow a sparse vector or an SDP-feasible matrix, and uses large-correlation graph structure to search candidate supports.

    Source: §2.1 · p. 8

  • Results

    For k = exp(√log d/C), the algorithm runs in O(d^2) time and returns a relaxed witness of value greater than 1 when ∥M∥op,k > 2, otherwise certifying ∥M∥op,k ≤2.

    Source: §1.2 · p. 4

  • Takeaways & Limitations

    The controlled increase in output sparsity yields quadratic-time algorithms in the highly sparse regime while preserving sample-complexity guarantees for well-behaved distribution families.

    Source: §4 · p. 38

    The vector certificate can be O(k^2)-sparse, so the stability result must be applied at that larger sparsity and requires eO(k^4) samples.

    Source: §3.2 · pp. 34–35

Abstract

from arXiv · show

We study fast algorithms for sparse-PCA certification. Given a positive semidefinite matrix $M$, the problem asks either to rule out a large $k$-sparse quadratic form or to return a high-value (relaxed) witness. The standard semidefinite relaxation provides such certificates, but existing general-purpose solvers require $\Omega(d^4)$ time. We give a bicriteria algorithm running in $O(d^2+d k^{O(\log k)})$ time: if some $k$-sparse unit vector has quadratic form greater than $2$, it returns either an $O(k^2)$-sparse unit vector or an SDP-feasible matrix of value at least $1$. For $k\leq\exp(O(\sqrt{\log d}))$, this running time is $O(d^2)$. We also go below the quadratic barrier in the sample-access model: Given $n=d^{o(1)}$ samples, our algorithm obtains a related one-sided certificate in $d^{2 - \Omega(1)}$ time for $k=\mathrm{polylog}(d)$, without forming the empirical covariance matrix. As an application, these certificate routines yield the first quadratic and subquadratic-time algorithms for robust sparse estimation for broad families of distributions. Our sparse-PCA algorithm reduces a high-value sparse direction to a bounded-radius set in the graph of large correlations and searches the resulting candidate supports. The subquadratic implementation constructs this graph using fast correlation detection.

1 Introduction

Sparse PCA certification asks whether a positive semidefinite matrix has a large quadratic form on a sparse vector, but the standard SDP solvers require Ω(d^4) time. The paper relaxes the witness form and develops fast certificates, then applies them to robust sparse mean estimation.

1.1 Motivation

  • The relaxation permits either a projector onto a C0k^2-sparse unit vector or a standard SDP-feasible matrix, while retaining an upper-bound certificate for the sparse operator norm.For light-tailed distributions, O(k^2 log d) samples suffice for the empirical relaxed value to approximate its population value to constant accuracy.Source: §1.1 · p. 3
  • Sparse-PCA certification matters for robust estimation because filtering uses high-value witnesses to score outliers, and standard SDP-based filtering inherits Ω(d^4) runtime.The paper targets highly sparse k = polylog(d) settings and studies both population and empirical covariance matrices.Source: §1.1 · pp. 2, 4, §1.2 · p. 6

1.2 Our results

  • For k = exp(√log d/C), with sufficiently large universal C > 0, the algorithm runs in O(d²) time and either returns a relaxed witness with value greater than 1 or certifies ∥M∥op,k ≤ 2.This improves on the stated Ω(d⁴) running time of the standard SDP approach.Source: §1.2 · p. 4
  • The quadratic-time algorithm has an approximation–runtime tradeoff: for any L ≥1, it runs in O(d^2 + d k^O(L)) and returns a certificate of value at least k^-1/(2L).A sufficiently large constant L gives a d^2poly(k)-time algorithm with a k^η approximation factor for small constant η.Source: §1.2 · p. 5
  • In the sample-access model, the subquadratic method uses fast correlation detection to construct a correlation graph without forming the full empirical covariance matrix.When a sparse target direction has sufficiently large value, the method reduces the search to a bounded-radius support family in the graph of large correlations.Source: §1.1 · p. 4, §1.2 · p. 5
  • For distributions with bounded covariance and bounded coordinate fourth moments, the heavy-tailed robust mean estimator uses n = O(k^4 log(d)/ϵ) samples and runs in eO(d^2k^O(log k)/ϵ^2) time with error O(√ϵ).The guarantees are stated for a k-sparse mean and ϵ-corrupted samples.Source: §1.2 · p. 6
  • For identity-covariance subgaussian distributions, the robust mean estimator uses n = O(k^2 log(d)/ϵ^2) samples, and the paper reports first broad-family algorithms with sparsity-respecting sample complexity and quadratic ambient-dimension runtime.The reported error guarantees are information-theoretically optimal for the stated distribution families.Source: §1.2 · p. 6
  • The paper also gives subquadratic variants of the robust sparse mean estimators, at the cost of increased sample complexity.The same approximation–runtime tradeoff lets smaller L reduce runtime's dependence on k while increasing error; taking L = Θ(log k) recovers the near-optimal error guarantees.Source: §1.2 · pp. 6–7

2 Fast algorithm for Sparse PCA

The section develops correlation-graph methods for sparse-PCA certification, reducing a high-value sparse direction to a bounded set of candidate supports and enabling a higher-value, potentially less sparse vector or SDP witness. It also describes runtime–target-value tradeoffs and sample-access approaches that build and search the graph without forming the full covariance matrix, including population-covariance certificates from empirical data.

2.1 Graph Connectivity and One-Step Truncated Power Method

  • A truncated power step with r ≥ β²/τ² either finds a vector of value at least β or retains every coordinate correlated with the starting coordinate by at least τ.Repeating the discovery step can explore a target support when it is connected in the large-correlation graph.Source: §2.1 · pp. 8–9
  • If a k-sparse witness of value at least β lies in a set of correlation radius L, the search returns an r-sparse vector of value above β or at most d(L + 1) candidate supports, one containing the witness support.Under the theorem’s conditions, each candidate support has size at most (r + 1)L.Source: §2.1 · pp. 9, 11
  • The candidate supports can be processed by a constrained power method to return a high-value sparse vector, or by an SDP relaxation to obtain a feasible matrix with large objective value.The vector guarantee permits sparsity up to max{r, (r + 1)L}; the SDP consequence is presented as better suited to downstream robust sparse mean estimation.Source: §2.1 · pp. 11–12
  • Any k-sparse unit vector of value at least R has a τ-connected sub-support with value at least R − τk, enabling a worst-case guarantee via bounded-radius search.The resulting constrained-power procedure uses search radius L = k when R − τk ≥ β + η.Source: §2.1 · pp. 13–14

2.2 Finding a small-radius witness

  • The next subsection motivates improving the fixed-parameter guarantee by noting that the branching search’s dependence on k is controlled by the radius of the connected component explored.This part introduces that radius-based motivation but does not provide the subsequent improvement’s result.Source: §2.2 · p. 14
  • A sparse witness of value R contains a subset whose large-correlation graph has radius at most L and whose quadratic value loses a factor of about k^(1/(2L)), plus thresholding error.Thresholding correlations below τ incurs additive error δ = τk.Source: §2.2 · p. 14
  • Under the stated PSD conditions, the algorithm returns either a high-value sparse vector or an SDP-feasible matrix, with the constrained power-method guarantee holding with probability at least 1−δ.The constrained power-method output has sparsity at most max{r, (r + 1)^O(L)} and value at least β; the SDP alternative has value at least β.Source: §2.2 · p. 17
  • For r = poly(k), constant L gives polynomial dependence on k for root-k target values, while L = C log k yields a k^O(log k) guarantee for a constant approximation.The radius-L search uses candidate supports of size (r + 1)^O(L) when the radius-reduction lower bound exceeds the certificate level by the approximation slack.Source: §2.2 · pp. 16–17

2.3 Faster algorithm through Correlation Detection

  • For empirical covariance with entry-query access, the algorithm checks graph density, uses correlation detection in the sparse case, and branches on the resulting graph rather than forming the full covariance matrix.The graph has at most dr edges in the sparse case, and candidate-support computation runs in time linear in graph size.Source: §2.3 · pp. 17–18
  • With (r + 1)-PSD input, rτ^2 > β^2, and B ≥ 2dr, the density check returns an r-sparse vector of value above β with probability at least 1−δ when the large-correlation graph has at least B edges.If it does not return such a vector, the graph has fewer than B edges.Source: §2.3 · pp. 18–19
  • When at most s off-diagonal pairs have covariance magnitude at least τ and ρ > 12τ, randomized covariance detection finds all pairs with magnitude at least ρ with probability at least 1 − δ.This adapts correlation detection from using the real-to-Boolean reduction in, and thresholds raw covariance entries rather than normalized correlations.Source: §2.3 · p. 21
  • If unit v has ∥v∥₀ ≤ k, v⊤Σv ≥ β + η, supp(v) ⊆ E, and E’s ρ-correlation radius is at most L, Algorithm 4 returns with probability at least 1 − δ either a unit u with ∥u∥₀ ≤ r_dense and u⊤Σu > β, or a family B of candidate supports.Family B has at most d(L + 1) supports, each of size at most (r_sparse + 1)L.Source: §2.3 · p. 22
  • For k = polylog(d), the constant-gap specialization yields a subquadratic-time sparse-PCA certificate, with correlation-detection exponent 1.62 + O(1/γ) < 2 for sufficiently large γ.The specialization uses β = 1, η = 1/10, ρ = 1/(4k), τ = (100k)^−γ, and L = max{1, ⌈C log k⌉}.Source: §2.3 · p. 24

2.4 Empirical Access and Sample Complexity

  • With probability at least 1 − δ, processing candidate supports by constrained power or SDP yields a vector of value at least β, or an SDP-feasible matrix of value at least β.The empirical guarantee assumes a sparse population witness with the stated correlation-radius condition; the SDP branch requires n ≥ C max{r, k^2} log(d/δ)/η^2 samples and returns a vector with sparsity at most r or a feasible matrix, both with population value at least β − η.Source: §2.4 · p. 25
  • For constant-gap sparse PCA, O(k^2 log(d)) samples and probability at least 2/3 suffice for an O(k^2)-sparse vector or an SDP-feasible matrix, each with population value at least 9/10.The stated running time is O(d^2k^2 log(d) + dk^O(log(k))); the section also notes that the vector route has higher dependence on k and larger output sparsity than the relaxed certificate.Source: §2.4 · p. 25

3 Robust Sparse Mean Estimation

This section applies sparse-PCA certificates to robust sparse mean estimation for heavy-tailed and identity-covariance subgaussian distributions, using stability and filtering to derive guarantees. For subgaussian data, it gives quadratic- and subquadratic-time variants, while heavy-tailed sample dependence is limited by certificates that may be k²-sparse.

3.1 Reduction of Robust Mean Estimation to Sparse PCA

  • Under stability and sparse-PCA certificate conditions, iterative filtering estimates the mean in sparse norm, using matrix or vector certificates to score points and a No certificate to terminate.The certificate routine either rules out a large k-sparse quadratic form or returns a matrix or vector witness; filtering removes high-scoring points.Source: §3.1 · pp. 27–28

3.2 Heavy-Tailed Distributions

  • For heavy-tailed data, median-of-means preprocessing reduces the problem to constant contamination, and stability after preprocessing enables certificate-based sparse mean estimation [DKLP22].The preprocessing aggregates groups of samples; the cited stability result transforms the data before the Section 3.1 framework is applied.Source: §3.2 · pp. 30–31
  • O(d^2 k^O(L) log^2(d) log^3(1/δ)/ε^2) is the running time of the heavy-tailed robust sparse mean estimator, with success probability at least 1−δ.The stated setting assumes covariance operator norm at most 1 and coordinatewise fourth moments O(1).Source: §3.2 · p. 32
  • For heavy-tailed data with bounded covariance operator norm and coordinate variances, Corollary 3.9 gives an estimator under n≫k^O(γ) log d+log(1/δ).The supplied corollary passages do not include its estimation-error or runtime formula.Source: §3.2 · p. 33
  • The heavy-tailed argument requires eO(k^4) samples rather than the eO(k^2) dependence achieved by [DKLP22], because its certificate may be k^2-sparse.Stability must therefore be invoked at sparsity O(k^2); recovering eO(k^2) would require different preprocessing or a certificate vector with O(k) sparsity.Source: §3.2 · pp. 34–35

3.3 Identity-Covariance Subgaussian Distributions

  • Shifting the empirical covariance by (1−κ)I makes near-one sparse variance detectable at scale κ, because clean shifted covariance is only O(κ).The sparse-PCA certificate is computed on the shifted matrix, while filtering retains the prior score definition.Source: §3.3 · p. 35
  • For identity-covariance subgaussian data, Corollary 3.12 gives a quadratic-time estimator when n≫k^2(log d+log(1/δ))/ϵ^2, succeeding with probability at least 1−δ.The displayed sparse estimation-error bound is truncated in the supplied passage.Source: §3.3 · pp. 35–36
  • Corollary 3.13 establishes a subquadratic-time robust sparse-mean estimator for identity-covariance subgaussian data, with sample, error, and runtime guarantees.The supplied corollary passages omit the formulas for these guarantees.Source: §3.3 · p. 36

4 Conclusion

The paper relaxes sparse PCA by allowing an f(k)-sparse vector alongside the standard SDP, enabling quadratic-time algorithms in the highly sparse regime while preserving sample-complexity guarantees for well-behaved distributions. The conclusion also identifies d^2 · poly(k) time as an open goal and distinguishes AI-assisted from independently developed results.

4 Conclusion

  • Allowing an f(k)-sparse vector alongside the standard SDP yields quadratic-time algorithms in the highly sparse regime while preserving sample-complexity guarantees for well-behaved distributions.The authors suggest controlled increases in output sparsity may also speed other sparse-estimation problems.Source: §4 · p. 38
  • The main open question is whether an algorithm can achieve d^2 · poly(k) running time.Source: §4 · p. 38
  • GPT-5.5-assisted investigations led to the restarted truncated-power method results, while the reduction to relaxed sparse PCA, subquadratic algorithm, SDP sample-complexity observation, and robust mean applications were developed independently.The authors state that they independently verified the manuscript’s mathematical arguments, results, citations, and conclusions and take responsibility for its content.Source: §4 · p. 38

Supplementary Material

The supplementary material organizes background facts, proofs, and supporting lemmas across Sections A–F.

Supplementary Material

  • Sections A–F cover related literature, facts and lemmas, covariance detection, its shifted sparse-PCA variant, subgaussian stability, and a restarted truncated-power-method counterexample.Source: Supplementary Material · p. 42

A Related work

The related work distinguishes this paper’s fixed-matrix, bicriteria sparse-PCA certification problem from statistical recovery tasks and prior structured algorithms. It also places the robust sparse-estimation results between broad but slower SDP methods and faster methods for highly structured distributions.

A Related work

  • Sparse-PCA literature spans worst-case sparse quadratic-form optimization, statistical estimation of a sparse leading component, and sparse-spike detection, whereas this paper studies a fixed-matrix bicriteria gap problem.Prior results primarily address exact-sparsity optimization or model-based recovery.Source: A Related work · p. 42
  • Unlike [KSTZ26], this work assumes neither a sparse population leading eigenvector nor an eigengap, and its fixed-matrix counterexample does not contradict that paper’s statistical guarantee.[KSTZ26] assumes independent subgaussian samples and fresh sample blocks across iterations.Source: A Related work · p. 42
  • Unlike [DZZ25]’s block-size-dependent runtime and additive-error guarantee, this method uses a bounded-radius component around the unknown witness to obtain a one-sided multiplicative-gap certificate.Both approaches threshold the matrix; this one returns an enlarged-support vector or an SDP witness.Source: A Related work · p. 42
  • Prior robust sparse-estimation work includes computationally efficient frameworks, filtering, convex and nonconvex methods, and efforts to relax distributional assumptions or improve error under weaker contamination models.The broader robustness-efficiency program also covers dense mean, covariance, PCA, list-decoding, and regression problems.Source: A Related work · pp. 42–43
  • Existing broad-family SDP algorithms for robust sparse mean estimation run in Ω(d^4) time, while faster quadratic or subquadratic methods target highly structured distributions; this work extends fast algorithms beyond that setting.The cited faster methods exploit a Gaussian-specific bounded-variance property of quadratic forms that need not hold for general identity-covariance subgaussian distributions.Source: A Related work · p. 43

B Omitted Facts

The omitted facts support candidate-support eigenvalue tests, covariance concentration, and filtering-based mean-estimation arguments.

B Omitted Facts

  • O(d^2 log d) time suffices for the random-start power-method bound when γ and δ are fixed constants and λ2 ≤ (1 − γ)λ1.The ordinary power method is used to test the largest eigenvalues of candidate-support matrices.Source: B Omitted Facts · pp. 43, 45
  • Fact B.3 states a concentration result for empirical covariance from i.i.d. mean-zero subgaussian vectors with covariance Σ.Source: B Omitted Facts · p. 45
  • Fact B.4 gives simultaneous covariance control over matrices with bounded entrywise ℓ1 norm.Source: B Omitted Facts · p. 46
  • Lemma B.7 links its stopping condition to sparse-norm accuracy under assumptions on contamination, mean stability, and sparse-direction covariance.Source: B Omitted Facts · p. 48
  • The randomized score-filtering process removes at most three times the initial number of corrupt samples with probability at least 2/3, and has at most |T(0)| rounds.Each nonterminal round deletes a maximum-score sample with probability one.Source: B Omitted Facts · p. 49

C Fast Covariance Detection

This section reduces fast covariance detection to Boolean correlation detection by padding coordinate vectors to equalize their norms and projecting them to low dimension. The resulting randomized algorithm finds coordinate pairs with covariance at least ρ, under a bound on the number of pairs above τ.

Fast Covariance Detection

  • At most s coordinate pairs with |Σ_ij| ≥ τ suffices for the randomized detector to output all pairs with |Σ_ij| ≥ ρ, with probability at least 1 − δ.The thresholds satisfy ρ > 12τ; the lemma states a running-time bound, but its expression is not present in the supplied passage.Source: C Fast Covariance Detection · p. 49

Reduction to correlation detection

  • The reduction treats centered data coordinates as vectors, pads each in a distinct orthogonal direction to equalize norms, then applies correlation detection.Gaussian projection reduces the effective dimension to O(log d), avoiding a dependence on the padded dimension n + d; the diagonal padding can be projected implicitly.Source: C Fast Covariance Detection · p. 49

Projection and Boolean detection

  • Gaussian-sign projection converts real-valued correlations into Boolean correlations, enabling the Boolean correlation-detection theorem to identify large covariance pairs.The proof applies the projection to padded data rows and uses a strong threshold separated from the margin threshold.Source: C Fast Covariance Detection · pp. 49–50

Verification and implementation

  • The proof verifies reported candidates and evaluates their covariance only after projection leaves at most s pairs above the margin threshold.The padding is applied implicitly: XG1 + PG2 is computed in O(ndm + dm) time without materializing the dense padded matrix.Source: C Fast Covariance Detection · p. 51

D Subquadratic Sparse PCA for Shifted Matrices

For a diagonally shifted empirical covariance matrix, the section extends the sparse-PCA branching search by detecting the correlation graph from the unshifted covariance. Under stated assumptions, it returns either a sparse vector certificate or candidate supports that can be used to obtain an SDP certificate.

Shifted-matrix reduction

  • The covariance detector builds the off-diagonal graph from empirical covariance Σ, while the remaining sparse-PCA computations use the shifted matrix A = Σ − λI.The diagonal shift leaves off-diagonal entries unchanged, so the graph is suitable for the shifted-matrix routines.Source: D Subquadratic Sparse PCA for Shifted… · pp. 51–52

Shifted support recovery

  • The listed alternatives are a unit vector u with ||u||0 ≤ r_dense and u⊤Au > β, or a matrix X ∈ XSDP,k supported on at most (r_sparse + 1)L coordinates with ⟨A, X⟩ ≥ β.The assumptions include ρ > 12τ, d^1.1 ≥ 2d r_dense, and A being max{r_dense + 1, r_sparse + 1}-PSD. The candidate family B has at most d(L + 1) supports, each of size at most (r_sparse + 1)L.Source: D Subquadratic Sparse PCA for Shifted… · pp. 51, 53

Algorithm 6

  • The algorithm first checks the diagonal and density, then detects covariance pairs and runs the branching search on the returned graph.The diagonal scan can immediately return a 1-sparse vector if A_ii > β; the detector uses D bounded by max{2ρ, β + λ}.Source: D Subquadratic Sparse PCA for Shifted… · p. 52

Semidefinite-relaxation certificate

  • The SDP corollary returns either a vector with u⊤Σu > β + λ or a feasible trace-one matrix supported on at most (r_sparse + 1)L coordinates with shifted objective at least β.It computes additive-η approximate SDP solutions over the candidate supports; the hidden constant in the final exponent depends on the SDP solver.Source: D Subquadratic Sparse PCA for Shifted… · pp. 52–53

E Proof of the Identity-Covariance Subgaussian Stability Lemma

This proof establishes identity-covariance subgaussian stability by combining sparse-direction concentration with a Gaussian representation argument for the SDP stability condition. With the stated sample size, the resulting sample is stable with high probability, alongside a lower sparse empirical-covariance bound.

XSDP,k-covariance stability

  • For the XSDP,k-covariance stability condition, the proof transfers a Gaussian deleted-sample bound to subgaussian samples using a three-Gaussian representation.The representation writes each subgaussian vector as a scaled sum of three marginally standard Gaussian vectors; the proof applies the Gaussian bound to each sequence.Source: E Proof of the Identity-Covariance… · pp. 53, 56, 57

Stability conclusion

  • For n independent samples from a mean-µ, identity-covariance subgaussian distribution on R^d, if k ≤ ℓ, ϵ ∈ (0, 0.01], δ ∈ (0, 1), and n ≥ C(((k^2 + ℓ) log d + k^2 log(1/δ))/ϵ^2), G is (ϵ, O(ϵ log(1/ϵ)), O(ϵ log(1/ϵ)), k, k, ℓ)-stable with probability at least 1 − δ.Source: E Proof of the Identity-Covariance… · p. 53

Sparse mean and rank-one covariance

  • Sparse mean and rank-one covariance stability hold simultaneously over every subset retaining at least (1 − α)n samples, by concentration and a union bound over deletion sets.The proof fixes each deletion set before concentration, then unions over deterministic deletion sets to cover data-dependent retained subsets.Source: E Proof of the Identity-Covariance… · pp. 54–55

Lower empirical covariance

  • The proof also establishes a lower ℓ-sparse empirical-covariance bound for every retained subset of size at least (1 − α)n.This is stated as an additional conclusion beyond the three conditions defining stability.Source: E Proof of the Identity-Covariance… · pp. 56–57

F A Counterexample to the Restarted Truncated Power Method

The section constructs a positive semidefinite counterexample in which restarted truncated power fails to approximate a high-value sparse direction, even with arbitrarily many iterations. The construction traps every restart trajectory on low-value supports despite a k-sparse vector of value 2.

Counterexample theorem

  • For r = ⌈Ck^2⌉, an instance has a k-sparse unit vector of value at least 2 while every restarted truncated-power iterate has value below 1.The result holds for every fixed C ≥ 1 and sufficiently large k, even with an infinite number of iterations.Source: F A Counterexample to the Restarted… · p. 58

Construction intuition

  • The quadratic form of truncated power is non-decreasing on PSD matrices, so the counterexample must prevent every trajectory from reaching a value comparable to the target.The section's branching-search remark says branching on the support of the first truncated multiplication from a signal coordinate includes the full target support and recovers value 2.Source: F A Counterexample to the Restarted… · pp. 58, 64

Signal trajectory trap

  • The construction couples each signal coordinate to F_i and then G_i so the trajectory leaves the full target support and becomes trapped on G_i plus one coordinate.The invariant supports have quadratic form below 4/5; additional P_a sets trap restarts from F coordinates.Source: F A Counterexample to the Restarted… · pp. 58, 61, 63
Loading 2609.09701v1…