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.

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

0 Answers1 Asked on January 1, 2022 by lawrence-mouill

curvature dg differential geometry metric spaces mg metric geometry riemannian geometry

1 Asked on January 1, 2022 by powertothepeople

2 Asked on December 29, 2021 by lao-tzu

1 Asked on December 29, 2021 by dimitri-koshelev

ag algebraic geometry algebraic curves birational geometry calabi yau elliptic curves

1 Asked on December 29, 2021

1 Asked on December 27, 2021

1 Asked on December 27, 2021 by bence-racsk

dg differential geometry gauge theory mp mathematical physics principal bundles reference request

1 Asked on December 27, 2021

1 Asked on December 27, 2021 by mcjr

0 Asked on December 27, 2021

1 Asked on December 27, 2021

2 Asked on December 27, 2021 by francesco-genovese

at algebraic topology homological algebra kt k theory and homology model categories

0 Asked on December 27, 2021

0 Asked on December 25, 2021

1 Asked on December 25, 2021

dg differential geometry ds dynamical systems flows symbolic dynamics

2 Asked on December 25, 2021

28 Asked on December 21, 2021 by kevin-buzzard

1 Asked on December 21, 2021

cv complex variables nt number theory riemann hypothesis riemann zeta function

0 Asked on December 21, 2021 by yupbank

Get help from others!

Recent Answers

- Philipp on How do i draw a ray in unity
- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- kjetil b halvorsen on How to test consistency of responses?
- eric_kernfeld on How to test consistency of responses?
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

© 2022 AnswerBun.com. All rights reserved.