PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse PCA via Covariance Thresholding

Yash Deshpande, Andrea Montanari

arXiv:1311.5179v5math.STstat.MLstat.TH

TL;DR

Sparse PCA support recovery remains difficult in regimes where prior SDP guarantees fail because their rank-one condition does not hold. This paper analyzes covariance thresholding and reports improved bounds over its preliminary version, alongside simulation evidence of a sharp sparsity threshold.

  • Problem

    The SDP support-recovery guarantee relies on a rank-one solution, a condition shown not to hold for √n ≲ s0 ≲ n/log p [KNV13].

    Source: §1 · p. 3

  • Method

    The paper analyzes a covariance thresholding algorithm for estimating sparse PCA support.

    Source: §1 · p. 3

  • Results

    The paper improves the bounds and expands the (s0, p, n) regimes yielding non-trivial results relative to.

    Source: §1 · p. 4

  • Takeaways & Limitations

    In simulations, covariance thresholding had higher success probability where diagonal thresholding began to fail, and its success probability increased with p for s0 ≤ 1.1√n.

    Source: §4 · p. 10

    The theoretical algorithm requires knowledge of s0, β, and θ, and its theory-suggested thresholds ρ and τ need not be optimal.

    Source: §4 · p. 10

Abstract

from arXiv · show

In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension $n\times p$ and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components $\mathbf{v}_1,\dots,\mathbf{v}_r$ has at most $s_0$ non-zero entries. We are particularly interested in the high dimensional regime wherein $p$ is comparable to, or even much larger than $n$. In an influential paper, \cite{johnstone2004sparse} introduced a simple algorithm that estimates the support of the principal vectors $\mathbf{v}_1,\dots,\mathbf{v}_r$ by the largest entries in the diagonal of the empirical covariance. This method can be shown to identify the correct support with high probability if $s_0\le K_1\sqrt{n/\log p}$, and to fail with high probability if $s_0\ge K_2 \sqrt{n/\log p}$ for two constants $0<K_1,K_2<\infty$. Despite a considerable amount of work over the last ten years, no practical algorithm exists with provably better support recovery guarantees. Here we analyze a covariance thresholding algorithm that was recently proposed by \cite{KrauthgamerSPCA}. On the basis of numerical simulations (for the rank-one case), these authors conjectured that covariance thresholding correctly recover the support with high probability for $s_0\le K\sqrt{n}$ (assuming $n$ of the same order as $p$). We prove this conjecture, and in fact establish a more general guarantee including higher-rank as well as $n$ much smaller than $p$. Recent lower bounds \cite{berthet2013computational, ma2015sum} suggest that no polynomial time algorithm can do significantly better. The key technical component of our analysis develops new bounds on the norm of kernel random matrices, in regimes that were not considered before.

1 Introduction

The introduction frames sparse PCA support recovery as a gap between attainable statistical recovery and computationally difficult regimes, then presents covariance thresholding as the paper’s focus. It reports improved bounds and broader regimes of nontrivial results over the preliminary version.

1 Introduction

  • Diagonal thresholding can recover support under the restricted equal-magnitude model when n ≳ s0^2 log p, while exhaustive support search needs n ≳ s0 log p.The exhaustive search has complexity of order p^s0.Source: §1 · p. 2
  • The SDP support-recovery guarantee requires a rank-one solution, but showed that this condition fails when √n ≲ s0 ≲ n/log p.The cited analysis also requires n ≥ K(β)s0 log(p−s0)/p.Source: §1 · p. 3
  • Recent results suggest polynomial-time support reconstruction is unavailable when s0 ≳ √n under a planted-clique complexity conjecture [BR13].The introduction contrasts this with statistical recovery up to s0 ≲ n/log p by exhaustive search.Source: §1 · p. 3
  • Covariance thresholding forms the empirical covariance, removes entries below τ/√n, computes a principal eigenvector, and thresholds its product with the original covariance to estimate support.The threshold τ is a suitably chosen constant; the approach was proposed in.Source: §1 · pp. 3–4
  • This paper improves the bounds and expands the regimes of (s0, p, n) with non-trivial results relative to its preliminary version.The proofs follow a similar strategy but are more careful.Source: §1 · p. 4

2 Algorithm and main results

Covariance thresholding estimates the low-rank population covariance by soft-thresholding a centered sample covariance, then uses the estimated components to recover their supports. The results give operator-norm covariance control, component estimates, and high-probability support recovery under stated conditions.

2 Algorithm and main results

  • The algorithm centers the first-half sample covariance, soft-thresholds its entries at τ/√n, then uses estimated components and the independent second half for support estimates.The data are split into two halves, with the second-half covariance used to construct support estimators.Source: §2 · pp. 4–5

2.1 Estimating the population covariance

  • For fixed ε, operator-norm covariance error below ε is sufficient when s0 ≲ ε√n, with the resulting rate depending on log(p/s0²) instead of log p.The theorem assumes n>C log p and n>s0².Source: §2.1 · pp. 5–6

2.2 Estimating the principal components

  • Under distinct spike strengths, the principal eigenvectors of the thresholded covariance provide estimates of the population components.Theorem 2 uses the threshold level from Theorem 1 and requires n>C log p, s0²<n, and s0²<p/e.Source: §2.2 · p. 6

2.3 Support recovery

  • Under A1–A2 and n>C log p, s0²<n, and s0²<p/e, covariance thresholding recovers the union of component supports with probability 1−o(1).A2 requires each nonzero entry to be at least θ/√s0 in magnitude and bounds ratios of entries where component supports overlap by γ.Source: §2.3 · p. 7

3 Algorithm intuition and proof strategy

Covariance thresholding uses sparsity to suppress dense covariance noise while retaining the sparse signal, and its analysis controls the resulting kernel-matrix perturbation. The section also explains why concentration must be established locally rather than through a global Lipschitz bound.

3 Algorithm intuition and proof strategy

  • In the high-dimensional regime, noise can dominate the sample covariance and make its principal eigenvector asymptotically orthogonal to the signal, motivating use of sparsity.The passage describes this contrast across the signal-strength threshold relative to √(p/n).Source: §3 · p. 8
  • Thresholding at order 1/√n can remove most dense noise while retaining the sparse signal when s0/√n is sufficiently small.The signal component is sparse, whereas the noise component is dense with entries of order 1/√n.Source: §3 · p. 8
  • Soft-thresholding bias scales as τ/√n per entry, with support size s0 contributing to the total bias bound.The accompanying argument identifies the s0 factor through the support size of vvT.Source: §3 · pp. 8–9
  • The analysis bounds the operator norm of the soft-thresholded kernel-matrix perturbation for p ≤ Cn and proves a modified bound for p > Cn.The perturbation has entries with variance δ(τ)/n, where δ(τ) is approximately exp(−cτ^2).Source: §3 · pp. 8–9
  • Earlier kernel-matrix results do not cover the paper’s soft-thresholding regime, including its non-smooth kernel and spectral-norm objective.The cited prior analyses address different spectral, asymptotic, or smooth-kernel settings.Source: §3 · p. 9
  • Because the Rayleigh quotient is not globally Lipschitz in the Gaussian data, the proof controls its gradient on typical inputs and applies concentration through an ε-net argument.This local-gradient approach is formalized in concentration lemma 5.4.Source: §3 · p. 9
  • Covariance Thresholding succeeds with high probability for s0 ≤ c√n, while Diagonal Thresholding requires a smaller support regime.The supplied figure passage gives c ≈ 1.1.Source: Figure 1 · p. 10

4 Practical aspects and empirical results

The practical section describes parameter-estimation and thresholding choices for a data-driven covariance-thresholding procedure, then compares its empirical support recovery with diagonal thresholding and vanilla PCA. The reported comparisons favor covariance thresholding in difficult or smaller-sample settings, while the data-driven procedure is not rigorously analyzed here.

4 Practical aspects and empirical results

  • Covariance Thresholding appears to have higher support-recovery success in the difficult regime where Diagonal Thresholding starts to fail.The empirical success probability is plotted against s0/√n for several p values, using 100 independent instances with p = n.Source: §4 · p. 10
  • For s0 ≤ 1.1√n, Covariance Thresholding’s empirical success probability increases with p, consistent with a sharp threshold at s0 proportional to √n.The reported curves become steeper as p increases.Source: §4 · p. 10
  • The theoretically analyzed algorithm requires s0, β, and θ, and its theory-suggested thresholds ρ and τ may not be optimal.The section introduces a data-dependent procedure to estimate parameters where possible.Source: §4 · p. 10
  • The data-driven procedure estimates noise scale from the median absolute deviation and uses thresholding to estimate the number of components and denoise eigenvectors.The threshold for covariance entries is chosen at the estimated noise level, and eigenvectors are subsequently hard-thresholded.Source: §4 · p. 11
  • The data-driven approach is not analyzed rigorously in this section, and its analysis is deferred to future work.The authors describe it as sharing the algorithm’s philosophy despite several differences.Source: §4 · p. 11
  • For the Three Peak and box examples, both thresholding methods perform well at large n, while covariance thresholding appears superior at smaller n.The simulations use the data-driven covariance-thresholding version on the Three Peak example and a similar box example.Source: §4 · p. 11

5 Proof preliminaries

The proof preliminaries set notation and collect tools used in the paper’s arguments. These include ε-net facts and a concentration lemma identified as a basic tool for establishing Theorems 2 and 3.

5.1 Notation

  • The notation section defines support sets, matrix and vector norms, restrictions and projections, and the paper’s soft-thresholding notation.It also specifies the large-n and large-p conventions used in theorem statements.Source: §5.1 · p. 12
  • The paper denotes each spike’s support by Qq, their union by Q, and writes η(·; ·) for the soft-thresholding function.The second argument of η is omitted when clear from context.Source: §5.1 · p. 12

5.2 Preliminary facts

  • An ε-net approximates every point of a set within ε, and the minimum size of such a net is its covering number.The preliminaries also state that ε-nets can be used to bound matrix spectral norms.Source: §5.2 · p. 13
  • The ε-net spectral-norm argument approximates a maximizing unit vector and bounds the resulting quadratic-form error by 2ε times the matrix norm.This follows from the stated approximation and Cauchy-Schwarz bound.Source: §5.2 · p. 13
  • The concentration lemma is presented as a basic tool for proving Theorems 2 and 3, with its proof using Maurey-Pisier and symmetrization arguments.The passage also identifies an independent Gaussian copy in the lemma’s setup.Source: §5.2 · pp. 13–14

6 Proof of Theorem 1

The section proves Theorem 1 by decomposing the thresholded covariance and bounding its signal, noise, cross, and diagonal terms across threshold regimes; it also derives Theorem 4 from these component bounds. It establishes Propositions 6.3–6.5 by controlling covariance components and applying concentration bounds and a standard argument.

6.1 Proof of Proposition 6.1

  • For τ < √log p/2 and n > C log p, the noise term N has small operator norm with probability 1 − o(1).Proposition 6.1 further establishes a rate of decay with the threshold level τ; its precise bound is not visible in the supplied passages.Source: §6 · p. 16, §6.1 · pp. 20, 24

6 Proof of Theorem 1

  • The cross and diagonal terms C and D are negligible, while for τ ≥ C0(β ∨ 1)√log p, N and C vanish entirely.The proof uses these bounds together with the signal and diagonal bounds to handle the higher-threshold regime.Source: §6 · pp. 16–17
  • Theorem 4 states that, under β ≤ C0, n > C1 log p, and τ ≤ √log p/2, its stated conclusion holds with probability 1−o(1).Its proof adds the error terms from Propositions 6.1, 6.2, 6.3, and 6.4, noting that β is bounded.Source: §6 · p. 18

6.3 Proof of Proposition 6.3

  • For Proposition 6.3, the proof uses this setting of A to obtain the form of Δ* required for the proposition.The cited lemma assumes τ ≤ √log p/2; the proof also bounds P{Gc} ≤ Cp^2 exp(−min(n, √p)/C) for some absolute C.Source: §6.3 · pp. 27, 30, 31

6.4 Proof of Proposition 6.4

  • For Proposition 6.4, a χ² Chernoff bound and union bound yield the stated bound with probability 1 − o(1), under (log p)/n < 1.The passage does not provide the bound’s expression.Source: §6.4 · p. 31

6.5 Proof of Proposition 6.5

  • For Proposition 6.5, the proof follows a standard argument [BL08b, Lemma A.3], taking τ ≥ C0(β ∨ 1)√log p for sufficiently large absolute C0.The passage also notes that conditioning, as in the proofs of Propositions 6.1 and 6.3, can prove the same result.Source: §6.5 · p. 31

7 Proof of Theorems 3

The proof controls the relevant error terms and establishes support containment with high probability. It then verifies that the sufficient conditions for the theorem follow from its assumptions.

7 Proof of Theorems 3

  • The proof controls the maximum T-term errors across indices i and components q, with ε measuring the largest principal-vector estimation error.The analysis conditions on U and takes expectation over Z.Source: §7 · p. 32
  • With high probability, the estimated support satisfies Q_q ⊆ Q̂_q ⊆ Q for every q.Here Q_q is the true support and Q̂_q is defined by thresholding the corresponding covariance-vector product.Source: §7 · p. 33
  • The proof gives sufficient conditions for the theorem’s conclusion and states that Theorem 3’s assumptions imply them.The implication uses s0 log p ≤ s0^2.Source: §7 · p. 34

Related papers

Loading 1311.5179v5…