Sparse signal recovery (nonlinear case)

Let $$K subset mathbb{R}^n$$, it may be that $$K$$ is "very thin" (e.g. $$K$$ is a $$k$$-dimensional affine subset of $$mathbb{R}^n$$, with $$k ll n$$). I’m interested in the case where $$K$$ is nonconvex, but for theoretical elegance, one can begin with the case where $$K$$ is indeed convex. Let $$s ll n$$ (the "sparsity"). Consider the sparse signal recovery problem:
$$tag{1} label{e:genprob} text{Find } x^* in K text{ such that }|x^*|_0 leq s,$$
where $$|cdot|_0$$ counts the number of nonzero entries.

My question: Although eqref{e:genprob} is NP-hard in general, in some cases (almost any affine $$K$$, using LASSO/compressed sensing/convex optimization/$$ell^1$$ regularization) one can solve eqref{e:genprob} in polynomial time. As far as I can tell, these efficient algorithms do not work when $$K$$ is a general convex set (or worse, a fully general set!) Can anyone point me to some literature/algorithms for solving eqref{e:genprob}, e.g. when $$K$$ is convex, with the same or similar astonishing efficiency of the LASSO/compressed sensing? Are there any books or papers on this? Is there a theory for it? Is it an open problem? Aside from the convex optimization/compressed sensing/LASSO literature, I also looked in "random sampling" (linear algebra) because I use that, but didn’t find it there either.

Mathematical discussion

This is related to sparse signal recovery, in the following way. Assume that $$f(x)$$ is some function, and consider the problem:
$$label{e:optprob} alpha^* = tag{2} inf_{x in mathbb{R}^n} f(x).$$
One assumes there is some $$x^*$$ with $$|x^*|_0 = s$$, such that $$f(x^*)$$ is minimal. Then, problem eqref{e:optprob} can be converted to problem eqref{e:genprob} by setting
$$tag{3} label{e:Kset} K = { x in mathbb{R}^n ; : ; f(x) = alpha^* }.$$
Consider the following relaxation of eqref{e:genprob}, eqref{e:Kset}
$$tag{4} label{e:lasso} inf_{z in mathbb{R}^n ; : ; |z|_1 leq t} f(z).$$
When $$f(x) = |b-Ax|_2$$ then $$K$$ is an affine subspace of $$mathbb{R}^n$$ and eqref{e:lasso} is called the LASSO method. It is well-known that, for almost every $$b,A$$ that have a sparse solution $$x^*$$ of eqref{e:genprob}, then $$z^*=x^*$$ when $$t = |x^*|_1$$. However, this quickly breaks down in the nonlinear case. For example, let $$K subset mathbb{R}^n$$ be a closed convex set that contains an $$s$$-sparse point $$x^*$$ and $$0 notin K$$, and define $$f(x) = d(x,K)$$ the Euclidian distance between $$x$$ and $$K$$. For almost any such $$K$$, eqref{e:lasso} fails to recover a sparse solution of eqref{e:genprob} for any $$tgeq 0$$.

I have been working on an alternate convex relaxation of eqref{e:genprob}, and I believe that my relaxation recovers the solution of eqref{e:genprob} with high probability even if $$K$$ is nonaffine. Because my relaxation is convex, it admits highly efficient solvers. I tried to find references on this, since it seems like a very canonical problem, and I have failed, to my surprise.

MathOverflow Asked by Sébastien Loisel on January 24, 2021

Related Questions

Fundamental ring of a circle

0  Asked on January 1, 2022 by tegiri-nenashi

Reference request: extendability of Lipschitz maps as a synthetic notion of curvature bounds

1  Asked on January 1, 2022 by lawrence-mouill

Should cohomology of $mathbb{C} P^infty$ be a polynomial ring or a power series ring?

1  Asked on January 1, 2022 by powertothepeople

Non-degenerate simplexes in a Kan complex

2  Asked on December 29, 2021 by lao-tzu

How to find a rational $mathbb{F}_{!q}$-curve on a quite classical Calabi–Yau threefold?

1  Asked on December 29, 2021 by dimitri-koshelev

Eigenvectors of random unitary matrices

1  Asked on December 29, 2021

Exceptional divisor of the Hilbert-Chow morphism of the punctual Hilbert scheme

1  Asked on December 27, 2021

Reference request: Gauge natural bundles, and calculus of variation via the equivariant bundle approach

1  Asked on December 27, 2021 by bence-racsk

How to solve numerically a system of 3 interdependent non-linear ordinary differential equations?

1  Asked on December 27, 2021

Non existence of stable vector bundles on $mathbb{P}^4$ with $c_1=0$ and $c_2=1$

1  Asked on December 27, 2021 by mcjr

If $f:U_1tomathcal L^p(mu;E_2)$ is Fréchet differentiable, can we say anything about the Fréchet differentiability of $umapsto f(u)(omega)$?

0  Asked on December 27, 2021

Convergence properties of related series

1  Asked on December 27, 2021

If $A$ is a cofibrant commutative dg-algebra over a commutative ring of characteristic $0$, then its underlying chain complex is cofibrant

2  Asked on December 27, 2021 by francesco-genovese

Rowmotion for general lattices

0  Asked on December 27, 2021

Is $mathrm{End}-{0}=mathrm{Aut}$ for derivation Lie algebra?

0  Asked on December 25, 2021

Explicit transitive flow on disc

1  Asked on December 25, 2021

Multiplicative and additive groups of the field $(prod_{ninomega}mathbb{Z}/p_nmathbb{Z})/simeq_{cal U}$

2  Asked on December 25, 2021

Which mathematical definitions should be formalised in Lean?

28  Asked on December 21, 2021 by kevin-buzzard

Does the Riemann Xi function possess the universality property?

1  Asked on December 21, 2021

Convex hull of prefix sum of $n$ ordered random points

0  Asked on December 21, 2021 by yupbank