Has the theory of "compressed sensing" been generalized to any classes of convex optimization problems? I need to analyze a problem of the type
$$\min ||x||_0, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$ where $g(x)$ is some convex function and the $0$-norm counts the number of nonzero entries of the vector. A natural approach is to instead solve $$\min ||x||_1, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$ which is now a convex problem. The theory of compressed sensing consider the case when the constraint is of the form $Ax = b$, and identifies conditions on the matrix $A$ which often hold and which force the solution of the two problems to coincide. Has anyone studied cases of general convex (possibly nonlinear) constraints? That is, are there papers studying nonlinear convex constraints, and identifying conditions on them which hold often or generically, such that the solutions of the above two problems are the same?

In my case, the constraint $g(x) \leq 0$ happens to be an SDP constraint $A(x) \succeq 0$ where $A(x)$ is a symmetric matrix whose entries depend linearly on the vector $x$, and I'm especially interested in this case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.