I was maximising a likelihood function, which is convex. I know that the system has a K-sparse solution. I wanted to know the conditions (or some sufficient conditions) on the likelihood function under which l1-regularisation is guaranteed to give me the sparse solution.

In other words, I am trying to solve the following problem

$$\max_{x \in \mathbb{R}^n} f(x),$$

where $f$ is a concave function. However I know that the true solution is K-sparse. I wanted to know the conditions under which the following optimisation returns the correct solution

$$\max_{x \in \mathbb{R}^n} f(x) - \lambda ||x||_1.$$

I found online that if $f=||y-Ax||_2^2$, then we need $A$ to satisfy a property called the restricted eigenvalue property. I wanted to know if anything is known in the general case or even special cases where such guarantees were known.


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.