The Condition-Number Barrier in Sparse Least Squares

Overview§

This paper settles a conjecture by Axiotis and Sviridenko [AS21] for the sparse least-squares problem, establishing a tight conditional lower bound on the trade-off between sparsity, approximation error, and the restricted condition number. The result is proven under the randomized exact-volume Small-Set Expansion Hypothesis (SSEH) in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Notably, the original proof was generated by an automated Gemini-based agentic system at Google and later verified and cleaned by the authors.

Core Result§

For any fixed $\gamma \in (0,1]$, no randomized polynomial-time algorithm can, with probability at least $2/3$, produce a vector $x$ satisfying

$$ \lVert Ax-b\rVert_2^2 \leq \min_{\lVert z\rVert_0 \leq k} \lVert Az-b\rVert_2^2 + \varepsilon \qquad\text{and}\qquad s = \lVert x\rVert_0 = O\left(k \, \kappa_{s+k}^{1-\gamma}\right), $$

where $\kappa_r$ denotes the restricted condition number at sparsity level $r$.

This means that the linear dependence on $\kappa$ previously conjectured is unavoidable: any polynomial-time algorithm must either blow up the sparsity by a polynomial factor in $\kappa$ or fail to achieve $\varepsilon$-approximate optimality. The hardness holds even for rational matrices $A$ of full column rank, ruling out numerical precision caveats.

Technical Methodology§

The proof proceeds via a reduction from the Small-Set Expansion Hypothesis (SSEH). The authors construct a family of sparse least-squares instances from weighted regular graphs such that deciding approximability of sparse recovery on these instances is at least as hard as refuting SSEH.

Key technical ingredients include:

• Reduction framework: Starting from a graph $G=(V,E)$ with weights, they build a matrix $A$ and vector $b$ whose restricted condition numbers directly encode the spectral gap of $G$. Any algorithm that beats the conjectured sparsity-condition-number trade-off would imply an efficient algorithm for distinguishing small-set expanding graphs from non-expanding ones, contradicting SSEH.
• Restricted condition number: The quantity $\kappa_r$ is defined as the ratio of the largest to smallest singular value of $A$ restricted to $r$-sparse vectors. The reduction ensures that $\kappa_r$ grows exponentially with graph size, making the lower bound sharp.
• Randomized exact-volume SSEH: The authors use the exact-volume variant, which requires the SSEH to hold for graphs with a specified weight distribution. This is crucial for transferring the hardness to rational instances and for maintaining integrality in the construction.
• Full column rank: The construction ensures $A$ has full column rank, eliminating trivial degeneracies and aligning with standard sparse recovery assumptions.

Significance and Implications§

The result establishes the first rigorous lower bound for the condition-number barrier in sparse least squares, confirming that the linear dependence in prior algorithmic guarantees (e.g., from iterative hard thresholding or basis pursuit) cannot be improved in the worst case under standard hardness assumptions. This has practical relevance for compressed sensing, sparse regression, and feature selection, where condition numbers are often poorly behaved.

The use of a Gemini-based agentic system to discover the proof is a notable meta-contribution, demonstrating the potential of LLM-driven theorem proving for complex conjectures. The authors emphasize that the proof was independently verified and edited, so the contribution is not just an automated artifact but a human-checked mathematical result.

Illustrative Snippet§

While the paper is purely theoretical, the following Python snippet sketches how one might compute the restricted condition number for a synthetic sparse regression instance, highlighting the object at the center of the barrier:

import numpy as np

def restricted_condition_number(A, r):
    """Compute the ratio of max to min singular value over r-sparse subsets."""
    n, d = A.shape
    best_max, best_min = 0, np.inf
    from itertools import combinations
    for cols in combinations(range(d), r):
        M = A[:, cols]
        s = np.linalg.svd(M, compute_uv=False)
        best_max = max(best_max, s.max())
        best_min = min(best_min, s.min())
    return best_max / best_min

# Small synthetic problem
np.random.seed(0)
A = np.random.randn(20, 10)
kappa_2 = restricted_condition_number(A, 2)
print(f"Restricted condition number (r=2): {kappa_2:.2f}")

In practice, algorithms must cope with huge $\kappa$ values, and this paper proves that no polynomial-time method can amortize that cost without sacrificing sparsity—a fundamental limitation that practitioners should be aware of when applying sparse solvers to ill-conditioned data.