CS Paper Radar

Inapproximability of L1->L2 Subspace Distortion

Vijay Bhattiprolu

cs.CC ·submitted 2026-11-17 10:22 UTC · v1

Abstract

We show, assuming NP is not contained in randomized quasipolynomial time, almost polynomial factor inapproximability for maximizing the $\ell_2/\ell_1$ ratio over a real subspace -- a problem also known as subspace distortion. This is a central problem in compressed sensing but also has connections to many areas such as real error correcting codes, dictionary learning, hypercontractive operator norms, small-set expansion, quantum information and random matrix theory. Distortion seems to be at the heart of building inapproximability theory for continuous optimization. Extending our results to the case of $\ell_2/\ell_p$ for all $p<2$ would lead to a near characterization of the convex sets over which one can efficiently and approximately maximize an arbitrary quadratic form. A recurring obstruction appears in hardness considerations of distortion -- how does one use a sparsity measure to test proximity to an exponential sized discrete set over the reals? This issue also appears in a host of other problems that involve measures of sparsity, shortness, density or expansion. We believe hardness of distortion is an intermediate step to understanding the complexity of small-set expansion and quantum separability, both of which are important directions of research. The main insight in our hardness reduction is the construction of a randomized affine linear map $T:\mathbb{R}^n\to \mathbb{R}^m$ such that the distortion of $Tx$ measures proximity to the hypercube $\{\pm 1\}^{n}$. Crucial to our construction is subsampling $x$ at *all* dyadic sample sizes, which gives an inverse polylogarithmic gap. This is a highly non-local tester, and thus departs from the local testing paradigm in PCP theory. Our reduction is also quite succinct, and so it suggests a rather simple distribution of subspaces for which approximately finding a planted sparse vector is intractable.

Closest papers

Nearest neighbours by meaning across the whole index.

SparseStack Is an Optimal Oblivious Subspace Embedding

cs.DS math.NA ·2026-09-02 ·Diar Heidary
theory similarity 0.66
Abstract · The proof was developed with AI systems

We prove that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013): $m=O((d+\log(1/δ))/\varepsilon^2)$ rows and $s=O(\log(d/δ)/\varepsilon)$ nonzero entries per column for distortion $\varepsilon$ and failure probability $δ$ on any fixed $d$-dimensional subspace, with explicit constants. The proof turns random-matrix concentration into a problem in finite-dimensional linear algebra. A coupling first reduces the moment estimates to a model with independent finite-valued entries. We represent these variables by multiplication operators, so their matrix moments become exact matrix elements of a deterministic operator on a finite tensor product. The central estimate bounds the contribution of $\ell\ge1$ occupied sites sharing the external factor $\mathbb{R}^d$ by $d+\ell-1$ rather than $d\ell$, yielding additive dependence on the dimension and the moment order. This approach controls both spectral edges without Gaussian comparison. The main theorem has been formally verified in Lean 4.

0.40

Recovering linear images of sparse signals from indirect observations

cs.IT stat.MLcs.LGmath.OC ·2026-09-05 ·Anatoli Juditsky, Arkadi Nemirovski
hot direction similarity 0.64
Abstract

In this paper, we develop and analyze techniques for recovering a linear image $Bx$ of an unknown signal $x$ from indirect noisy observation $ω=Ax+ξ$. It is {\em a priori} known that $x\in \cX$, a given convex compact set, and that $x$ is $s$-sparse---has at most $s$ nonvanishing entries. The proposed estimates belong to a large family of recovery routines by $\ell_1$-minimization. However, unlike the classical result describing performance of such estimates, we do not make any special (and hard to check) assumptions about the sensing matrix $A$ such as nullspace or Restricted Isometry condition and the like. As a consequence, parameters of the estimates and the upper bounds on their risks are not available in a closed analytic form, but are delivered instead by efficient computation as solutions to explicit convex optimization problems.

0.26

Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation

cs.DS ·2026-08-26 ·Honghao Lin, Vahab Mirrokni, David P. Woodruff
theory similarity 0.60
Abstract

We study strong coresets for $\ell_p$ subspace approximation. Given a matrix $A\in\mathbb{R}^{n\times d}$, the goal is to sample and rescale a small number of its rows to obtain $SA$ such that $\left\|SA(I-P_F)\right\|_{p,2}^p=(1\pm\varepsilon)\left\|A(I-P_F)\right\|_{p,2}^p$ simultaneously for every subspace $F\subseteq\mathbb{R}^d$ of dimension at most $k$, where $P_F$ is the orthogonal projector onto $F$. Woodruff and Yasuda [WY25] (FOCS 2025) obtained coreset sizes $\widetilde{O}_p(k\varepsilon^{-4/p})$ for $1\leq p<2$ and $\widetilde{O}_p(k^{p/2}\varepsilon^{-p})$ for $p>2$. We improve these bounds to $\widetilde{O}_p(k\varepsilon^{-2})$ and $\widetilde{O}_p(k^{p/2}\varepsilon^{-2})$, respectively. For $1\leq p<2$, our algorithm runs in $\widetilde{O}_p(\mathrm{nnz}(A)+d^ω+k\varepsilon^{-2})$ time. The resulting coreset size matches the sampling lower bound [LWW21] up to logarithmic factors when $k+1\geq C\log(1/\varepsilon)$ for an absolute constant $C$. For $p>2$, our algorithm runs in $\widetilde{O}_p(\mathrm{nnz}(A)+d^ω)$ time, matching the running time of the framework of Woodruff and Yasuda. We use different techniques in the two regimes. For $1\leq p<2$, we combine a bicriteria low-rank split with Lewis-weight sampling and empirical-process bounds independent of the output dimension. For $p>2$, we give a sharper analysis of the Woodruff-Yasuda construction. By retaining the truncation in its sampling probabilities throughout the row-count recurrence, we show that it achieves the improved $\varepsilon^{-2}$ dependence.

0.25

One-Sided-Error Parameterized Reductions for the Minimum Distance and Shortest Vector Problems

cs.CC ·2026-08-14 ·Shuichi Hirahara, Kazuki Ogitsuka
theory similarity 0.60
Abstract · Full version of RANDOM 2026

It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error randomized reductions, Bennett, Cheraghchi, Guruswami, and Ribeiro (STOC 2023) proved parameterized hardness of approximation for these problems. We partially derandomize their reductions and present one-sided-error randomized reductions: MDP is W[1]-hard to approximate within an arbitrary constant factor under FPT many-one one-sided-error randomized reductions; For every $p \ge 1$, SVP in the $\ell_p$ norm is W[1]-hard to approximate within an arbitrary constant factor below $2^{1/p}$. We demonstrate the usefulness of one-sided-error randomized reductions by showing that they can be conditionally derandomized when the target problem has an OR function. Under a standard hardness-vs-randomness assumption, namely a plausible lower-bound assumption against nondeterministic circuits, we prove a general theorem formalizing this derandomization. Here, an OR function combines several instances into one instance that preserves their disjunction. We construct such OR functions for the relevant MDP and SVP gap problems, and thereby obtain deterministic W[1]-hardness for approximating MDP over every fixed finite field within every constant factor, and for approximating SVP in $\ell_p$ norms for every fixed integer $p$ within every factor below $2^{1/p}$. Applying the same framework to Micciancio's one-sided-error randomized reduction (ToC 2012) yields, under the same circuit lower-bound assumption, deterministic polynomial-time NP-hardness of approximating Euclidean SVP within every constant factor.

0.15

A Nonadaptive Sparse Fourier Transform in Every Dimension

cs.DS cs.ITmath.NA ·2026-11-19 ·Mahdi Cheraghchi, Jingyi Lyu
similarity 0.60
Abstract

Let $G=(\mathbb{Z}/2^a\mathbb{Z})^d$, of order $N=2^{ad}$. Given point-query access to any complex signal $X$ with Fourier transform $\hat{X}$ over $G$, we provide a randomized algorithm that constructs a $k$-sparse estimate $\widetilde{X}$ via non-adaptive queries such that, with large probability, $\|\widetilde{X}-\hat{X}\|_2^2 \leq C \cdot \|H_k(\hat{X})-\hat{X}\|_2^2$, for an absolute constant $C>0$, where $H_k(\cdot)$ denotes the best $k$-sparse approximation. The constant $C$ can be improved to any desired $1+\varepsilon$ by either supplying a constant-factor estimate on the $k$-sparse tail norm or allowing an arbitrarily small additive error term $δ\|\hat{X}\|_2^2$ on the right-hand side. With a supplied tail estimate, we can also satisfy an $\ell_\infty/\ell_2$ heavy hitters guarantee. For fixed $δ$, the number of samples is $O((k/\varepsilon^2)(\log N)\log(k/\varepsilon))$, and the recovery algorithm requires a polynomial in $(k/\varepsilon)\log N$ exact operations. The algorithm naturally extends to $G=(\mathbb{Z}/b^a\mathbb{Z})^d$ for any fixed integer $b>1$.

0.32

The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration

cs.DS ·2026-09-18 ·Tung Mai, Anup Rao
theory similarity 0.60
Abstract

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0 < δ< 1$, there exists a distribution that gives an OSE with embedding dimension $O((d + \log(1/δ))/\varepsilon^2)$ and column sparsity $s = O(\log(d/δ)/\varepsilon)$, with failure probability at most $δ$. We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.

0.36

Robust subspace designs and the power of a unique small quantum witness

cs.CC quant-phcs.DS ·2026-10-05 ·Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise, Partha Mukhopadhyay
publishedtheory similarity 0.60
Abstract

The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of subspaces that have small intersection with any given subspace of a fixed dimension. We introduce \emph{robust subspace designs}. Informally, these are a quantitative extension in which we demand that not too many subspaces of the family contain directions that lie close to any given subspace of a fixed dimension. We give a probabilistic construction of such a robust subspace design of polynomial size, as well as a non-trivial explicit construction of superpolynomial size. Our main application of this new concept is a quantum space-bounded variant of the Valiant-Vazirani theorem (Theor.Comput.Sci.'86), which shows that restricting $\mathsf{NP}$-complete problems to instances with at most one accepting witness preserves hardness under randomized reductions. For quantum witnesses, the analogous quantity is the dimension of an accepting witness subspace. We use our probabilistic construction of robust subspace designs to isolate a unique witness for space-bounded quantum Merlin-Arthur protocols with perfect completeness and an acceptance gap outside their perfectly accepting subspace. As further applications, we give a randomized reduction of well-conditioned nullity testing to space-bounded quantum Merlin-Arthur protocols with perfect completeness. Using a similar idea, we find that ordinary subspace designs allow us to recover the classical $\mathsf{C_= L}$ containment of Allender, Beals, and Ogihara (STOC'96) for general nullity testing through a simpler proof.

0.31

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

cs.IT math.PRcs.LGmath.CO ·2026-10-08 ·Thomas Weinberger
theory similarity 0.59
Abstract

For a known finite-dimensional model subspace, classical Gaussian regression theory guarantees that least squares eventually attains the parametric rate, with prediction error scaling as the subspace dimension divided by the sample size. Yet subspaces with the same number of unknown coefficients can require very different sample sizes to reach this regime. For subspaces of polynomials on the Boolean cube, a fundamental question is how restrictions on degree and ambient dimension jointly determine this threshold. Our main result sharply characterizes the worst-subspace minimax sample threshold over a substantial parameter range, revealing an exponential dependence on degree and precisely quantifying the joint effects of degree, ambient dimension, and subspace dimension. A small modification of our lower-bound construction reveals a strong separation: a single subspace can admit noiseless recovery with optimal sample complexity independent of degree, yet require essentially the worst-case sample size, exponential in degree, to attain the noisy parametric rate. To establish the sampling lower bound, we sharpen the Polyanskiy-Samorodnitsky uncertainty principle (J. Funct. Anal., '19) to uniformly optimal precision and extend its concentration guarantee to large subspaces in which every function concentrates most of its energy on one shared Hamming ball. The sampling upper bound follows from the sharp moment bound of Kirshner and Samorodnitsky (IEEE Trans. Inf. Theory, '21) combined with empirical-process bounds.

0.33