PaperlayerView exact revision on arXiv

Source-linked AI summary

Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

Richard Y. Zhang

arXiv:2608.29018v1stat.MLcs.ITcs.LGmath.OCmath.ST

TL;DR

The paper asks whether penalized rank-restricted matrix LASSO can achieve both the optimal recovery rate and the sharp RIP threshold at global minima. It develops a defect-preserving recovery argument and adversarial counterexamples, showing that the sharp threshold is attainable, unimprovable, and independent of search rank when the search space contains the ground truth.

  • Problem

    Prior analyses of penalized LASSO either sacrificed the sharp RIP threshold or the optimal error rate, while the estimator may have greater nuclear norm than the ground truth.

  • Method

    The proof retains an additive defect in the head-tail inequality and combines it with a sharp head estimate, while necessity uses a two-block adversarial construction.

  • Results

    If δ < δsharp(k/r⋆), every global minimizer achieves the stated optimal error bound, whereas beyond the threshold counterexamples can make every global minimizer fail; the threshold is therefore sharp.

  • Takeaways & Limitations

    At global optimality, the recovery threshold depends on the ground-truth rank rather than the search rank, so rank overparameterization is not itself a statistical obstruction.

Abstract

from arXiv · show

We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank $r_{\star}$, if the rank-$k$ RIP constant satisfies $δ<δ_{\mathrm{sharp}}(k/r_{\star})$, where $δ_{\mathrm{sharp}}(t)=t/(4-t)$ for $0<t<4/3$ and $δ_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}$ for $t\ge4/3$, then every global minimizer has Frobenius error $\lesssim\sqrt{r_{\star}}λ$ for all $λ\gtrsim\|\mathcal{A}^{*}(ξ)\|_{\mathrm{op}}$ and at every search rank $r\ge r_{\star}$. The constants depend only on the RIP constant and $t=k/r_{\star}$, and in particular are independent of the search rank. When the rank restriction is inactive, the result specializes to the ordinary convex matrix LASSO. We also obtain the analogous results for sparsity-restricted vector LASSO. Conversely, we show that the threshold $δ<δ_{\mathrm{sharp}}(k/r_{\star})$ cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.

I. INTRODUCTION

The paper characterizes recovery at global minima of rank-restricted matrix LASSO under RIP, obtaining a sharp threshold, optimal error scaling, and search-rank-independent guarantees. It also shows sharpness, convex-relaxation consequences, and the distinction between statistical recovery at global minima and the difficulty of finding them.

  • Problem and formulation: Low-rank matrix recovery estimates an unknown rank-at-most-r⋆ matrix from noisy linear measurements using a factored, rank-restricted LASSO formulation.The estimator can be viewed either as nonconvex optimization over factors or as nuclear-norm penalization with a rank cap.
  • Problem and formulation: The paper addresses recovery guarantees at global minima because existing second-order-critical-point guarantees require RIP orders that grow with the search rank.Those landscape conditions can become more demanding under overparameterization and may impose substantially higher measurement requirements.
  • Main guarantee: Under the theorem’s RIP assumptions, every global minimizer satisfies the stated error bound whenever δ < δsharp(k/r⋆), with hidden constants depending only on δ and k/r⋆.The theorem assumes rank(X⋆) ≤ r⋆, A ∈ RIP(δ,k), and λ > 0.
  • Main guarantee: The threshold is sharp: when δ ≥ δsharp(k/r⋆)+1/r⋆, counterexamples exist in which every global minimizer fails even in the noiseless case.For fixed t, this prevents uniformly relaxing the threshold as r⋆ grows.
  • Main guarantee: At λ ≍ ∥A*(ξ)∥op, the error bound is minimax optimal up to absolute constants under Gaussian noise.The constants in the bound do not depend on the search rank.
  • Consequences and scope: Making the rank cap inactive recovers the ordinary convex matrix LASSO, which inherits the same sharp threshold and error bound.This contrasts with prior penalized analyses that either used more conservative thresholds or obtained suboptimal error dependence.
  • Consequences and scope: The theorem guarantees recovery at a global minimizer for every search rank r ≥ r⋆, but does not provide an algorithm for finding that minimizer.Incremental lifting can certify global optimality, although its search rank may need to increase substantially; larger ranks also complicate the optimization landscape.

B. Extension to sparse-vector LASSO

The paper transfers its sharp rank-restricted matrix LASSO theory to sparsity-restricted vector LASSO, obtaining matching sufficiency and necessity thresholds and recovering the ordinary convex estimator when the sparsity cap is inactive.

  • Vector analogue: The vector theorem mirrors the matrix result by replacing target rank r⋆ with target sparsity s⋆ and using vector RIP.The proof first establishes the sparse-vector result, then transfers its singular-value geometry to matrices.
  • Computational analogy: The sparse and matrix formulations are computationally analogous: active-set enlargement corresponds to rank-incremental lifting until the cap or full LASSO optimality conditions are reached.Fixing an active set leaves a small convex LASSO, just as fixing search rank leaves a low-dimensional factored problem.
  • Sufficiency: If δ < δsharp(k/s⋆), every global minimizer of the sparsity-restricted vector LASSO satisfies the stated recovery bound, with constants depending only on δ and k/s⋆.The theorem assumes ∥x⋆∥0 ≤s⋆ and A ∈ rip(δ,k).
  • Necessity: If δ ≥δsharp(k/s⋆) + 1/s⋆, counterexamples exist in which every global minimizer fails to recover the ground truth, even when ξ = 0.The construction uses sparse targets with ∥x⋆∥0 ≤s⋆ and operators satisfying vector RIP at order k.
  • Convex specialization: Taking the search sparsity s=d removes the cap and yields the ordinary convex vector LASSO, for which the theorem gives a complete sharp-RIP guarantee.This parallels the rank-inactive specialization for the convex matrix LASSO.
  • Motivation: The penalized setting is harder than constrained recovery because LASSO solutions can have larger nuclear norm than the ground truth, so prior transfers sacrificed either sharpness or optimal error dependence.The paper’s result addresses this gap by attaining both the sharp threshold and the optimal error rate.

A. Why the Standard Proof Loses Sharpness

The standard LASSO proof enlarges the head–tail relation multiplicatively, which raises the feedback gain and loses the sharp RIP threshold. Prior results also suffer from conservative thresholds or Euclidean-noise dependence.

  • The sharp threshold is determined by the single gain condition ρδ,t < 1, equivalent to δ < δsharp(t).The resulting error rate is O(λ√r⋆).
  • The LASSO KKT condition controls the dual residual, but its nuclear-norm comparison can fail, yielding only an enlarged head–tail inequality.This enlargement is available under λ ≥ 2∥A*(ξ)∥op.
  • 3ρδ,t < 1 replaces the sharp condition ρδ,t < 1 when the tail is bounded coarsely by 3H.The factor-three enlargement preserves the statistical rate but triples the feedback loop gain.
  • Under Gaussian sensing, the Euclidean-noise calibration remains constant as m → ∞, whereas dual-noise calibration supports improved behavior with oversampling.Gaussian RIP holds with high probability once m ≳ δ^-2k(d1+d2).

III. LASSO RECOVERY GUARANTEES

The recovery proof introduces a head–tail defect to preserve the sharp feedback threshold for both vector and matrix LASSO. This yields explicit guarantees under δ < δsharp(t), with error controlled by the intrinsic rank or sparsity rather than the search size.

  • δ < δsharp(t) is equivalent to the contraction condition ρδ,t < 1 in the feedback argument.The margin 1−ρδ,t controls contraction, while τδ,t scales the measured-error contribution.
  • Under δ < δsharp(k/r⋆) and λ above the dual-noise level, every search rank r ≥ r⋆ satisfies the matrix LASSO recovery bound.The theorem’s constants depend on δ and t, while the guarantee applies at every admissible search rank.
  • The vector theorem has the same sharp threshold for every sparsity level r ≥ r⋆.The matrix result follows by applying the vector argument to the singular values of the error.
  • The proof decomposes error into a sparse head, diffuse tail, and a defect measuring violation of the exact head–tail relation.The head uses ℓ2 geometry, while the tail uses scale-normalized ℓ1 and ℓ∞ quantities.
  • The defect and best-r⋆ ordering control the tail without multiplying the head by a factor greater than one.This retains the sharp threshold that would be lost under the coarse bound T ≤ 3H.

A. Verification for the vector LASSO

The vector verification derives a global-optimality inequality from LASSO optimality, then transfers it to matrices through singular values. Matrix RIP becomes vector RIP along fixed singular directions, while norm and error identities preserve the conclusions.

  • Global optimality of the vector LASSO yields the basic perturbation inequality for σ = xλ,r − x⋆.The derivation expands the squared residual and applies the best-r⋆ ordering.
  • The matrix proof reduces to the singular values of E = Xλ,r − X⋆, with ∥σ∥2 = ∥E∥F and ∥σ∥1 = ∥E∥nuc.The induced sensing matrix satisfies Aσ = A(E).
  • The noise inner product is bounded by ∥A*(ξ)∥op∥E∥nuc, setting the dual-noise level λ0 = ∥A*(ξ)∥op.This is the matrix analogue of the vector dual-noise calibration.
  • Matrix RIP transfers to vector RIP because rank(U diag(z)Vᵀ) equals ∥z∥0 and its Frobenius norm equals ∥z∥2.The transfer applies to vectors supported on at most k coordinates.
  • Applying the vector result to singular values converts sparsity, ℓ1, and ℓ2 statements into rank, nuclear-norm, and Frobenius-norm statements.This completes the matrix theorem from the vector argument.

IV. NECESSITY BY COUNTEREXAMPLES

The necessity construction produces adversarial matrix and vector instances above the proposed threshold, with unique global minimizers that remain far from the ground truth. A two-block identity-minus-rank-one design tunes the RIP constant while preserving optimality.

  • For every ε > 0, counterexamples exist at RIP constants δsharp(t) + ε, so the threshold cannot be uniformly improved.The construction applies at fixed rank ratio t = k/r⋆.
  • The two-block construction places the ground truth and bad minimizer in orthogonal subspaces while annihilating their secant direction.Orthogonal directions supply subgradients establishing optimality, and α is tuned to achieve the target RIP constant.
  • The bad minimizer is unique and remains separated from the ground truth, with ∥Xλ,r − X⋆∥F ≥ ∥X⋆∥F.The failure holds for every search rank r ≥ C(t)r⋆.
  • The identity-minus-rank-one map has an exactly computable RIP constant, enabling construction at the desired rank k.Lemma 25 characterizes RIP through the largest eigenvalue of the associated matrix.
  • Integer rounding in the higher-order branch requires headroom δ − δsharp(t) ≥ 1/r⋆ to select the bad minimizer rank and tune α.Lemma 26 then guarantees the constructed map satisfies the required RIP condition.
  • The matrix counterexample transfers to the vector LASSO through a diagonal restriction preserving the recovery error.The vector instance inherits RIP and satisfies ∥xλ,r − x⋆∥2 = ∥Xλ,r − X⋆∥F.

V. PROOF OF PROPOSITION 14

The proof establishes the sharp RIP condition by decomposing the error into a sparse head and diffuse tail, then designing sparse atomizations whose accumulated RIP errors remain controlled. It combines the established high-order mechanism with a new lower-order construction.

  • The proof splits the error into a sparse head and a diffuse tail, then represents the tail using sparse pieces.
  • RIP preserves sparse-piece norms and controls measured inner products between disjoint pieces, enabling comparison with the whole error.
  • Convex atomization replaces rigid tail blocks with sparse atoms whose diffuse scale reduces the conservatism caused by spiky initial blocks.
  • The lower-order branch 2 ≤ k < 4r⋆/3 requires a new idea because high-order atomization misses the sharp threshold, while k < r⋆ places the full head outside the RIP order.
  • The proof uses head randomization and paired head-tail atoms to recover the sharp threshold for all k ≥ 2 and r⋆ ≥ 1.

A. High-order branch t ≥4/3

The high-order branch handles k ≥ 4r⋆/3 by separating large tail coordinates from a diffuse remainder, atomizing the remainder, and applying RIP to k-sparse combinations.

  • For k > r⋆, large tail coordinates are retained in a deterministic component while only the diffuse remainder is atomized.
  • The big–small atomization lemma supplies a finitely supported random vector for the small tail component.
  • The resulting vectors inside the comparison are k-sparse almost surely, so the rank-k RIP applies directly.
  • The high-order RIP comparison bounds the relevant quantity through upper and lower RIP applied to disjointly supported combinations.
  • The comparison yields the desired estimate, including the δ = 0 case by applying the argument with ε and letting ε decrease to zero.

B. Low-order branch 0 < t < 4/3

The low-order branch uses randomized head pieces paired with complementary tail atoms, allowing disjoint k-sparse sums to exploit cancellations unavailable to high-order atomization.

  • For 2 ≤ k < 4r⋆/3, the construction chooses complementary sparsity levels α and β for randomized head and tail pieces.
  • Uniformly sampled α-sparse and β-sparse head pieces are paired with β-sparse and α-sparse tail atoms, respectively.
  • Conditioning head samples to be disjoint lets their union use the full budget k = α + β.
  • The uniform sampling identities provide explicit first and second moments for the randomized sparse pieces.
  • Averaging the paired RIP inequalities creates the cancellations needed to recover the full sharp threshold.

2) Atomizing the tail:

Tail atomization converts a diffuse tail into sparse random vectors at prescribed sparsity levels while preserving its mean and controlling its second moment for the low-order construction.

  • The tail is diffuse at the scale T, which controls both its total mass and largest coordinate.
  • For every integer 1 ≤ s ≤ r⋆, polytope atomization produces a finitely supported random vector supported on the tail.
  • The atomization applies the sparse-polytope lemma with entry bound √r⋆T/s and supplies a second-moment estimate.
  • Randomizations with sparsities β and α provide the tail atoms used in the paired low-order construction.
  • When 1 < t < 4/3, an additional randomization with sparsity (t − 1)r⋆ = k − r⋆ is introduced.
  • The construction defines a comparison for disjointly supported vectors using positive integer sparsity parameters.

3) RIP comparisons:

The RIP comparison constructs averaged quantities that couple randomized head and tail pieces, then compares them across the regimes t<1 and 1≤t<4/3. These comparisons establish the key low-order inequality underlying the recovery threshold.

  • Cancellation identities: The construction is designed around two cancellations, obtained by substituting the head and tail decompositions into the relevant second-moment expressions.The proof uses independence, uniform head means, tail means, and the relation σtail=σ−σhead to simplify the cross terms.
  • Averaged quantities: X couples randomized head and tail pieces, while Y and Z reconstruct or augment head energy in the regimes t<1 and 1≤t<4/3.Every vector in X, Y, and Z is k-sparse because sampled head and tail supports are disjoint.
  • Regime-specific comparisons: For t<1, the proof compares X against Y; for 1≤t<4/3, it compares X against Z.The two comparisons use different constructions because Z exploits the additional k−r⋆ tail budget when t≥1.
  • RIP bounds: RIP lower and upper bounds are applied to the averaged quantities to produce the comparisons needed for the key low-order inequality.For t<1, the first norm receives lower RIP while the subtracted norm receives upper RIP; the same pattern is applied to X and Z for 1≤t<4/3.

VI. CONCLUSION

The conclusion establishes sharp recovery thresholds for global minima of rank-restricted matrix and sparsity-restricted vector LASSO. It emphasizes that global-minimum guarantees depend on the ground-truth complexity rather than the search rank, when the search space contains the truth.

  • Main conclusion: The paper establishes the sharp recovery threshold δ<δsharp(t) for global minima of rank-restricted matrix LASSO and sparsity-restricted vector LASSO.Here t=k/r⋆ for matrix LASSO and t=k/s⋆ for vector LASSO.
  • Proof strategy: The proof retains a defect term in the head-tail inequality, using an additive relation T≤H+D instead of a multiplicative relation T≤cH.This proof strategy is presented as the key idea for preserving the sharp threshold under penalized recovery.
  • Search-rank dependence: At global minima, the sharp recovery threshold depends only on the ground-truth rank and is independent of the search rank when the search space contains the ground truth.The conclusion contrasts this with the greater landscape complexity and stronger assumptions that can arise when increasing the search rank for second-order critical-point analyses.
Loading 2608.29018v1…