3
$\begingroup$

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.

$\endgroup$

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.