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 it is sufficient for $A$ to satisfy a property called the restricted isometry property. I wanted to know if anything is known in the general case or even special cases where such guarantees were known.

  • $\begingroup$ There are a couple of minor errors in your posting- first, in the maximization problem you want $f(x)=-\| y- Ax \|_{2}^{2]$. Second, the "restricted isometry property" is a sufficient but not necessary condition for the recovery of sparse solutions. There are many other sufficient conditions. $\endgroup$ – Brian Borchers Jul 29 '14 at 3:20
  • $\begingroup$ It might help if we knew more about the particular likelihood function $f(x)$ that you're working with. $\endgroup$ – Brian Borchers Jul 29 '14 at 3:20
  • $\begingroup$ @BrianBorchers: Thanks. Edited. The function I am looking for is something like $\sum_{i=1}^{n} log(a_i^tx) -a_i^tx$, which is concave as it is a composition of a concave function with a linear function. There seem to be many sufficient conditions for when $f(x)=||y-Ax||_2^2$, but I've not found anything on a general function. $\endgroup$ – Devil Jul 29 '14 at 15:32

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.