I'm looking to learn more about Sparse Optimization and apply it to machine learning problems. Could you please recommend some books/resources on this topic? Both theoretical and applied are fine.
1
-
$\begingroup$ This would be better asked at Computational Science site. You can ask a moderator to migrate the question there by flagging it, especially if you don't get answers here. $\endgroup$– 40 votesCommented Jul 28, 2013 at 19:39
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
First, just to clarify things, you're talking about solving optimization problems of the form
$\min \| x \|_{1}$
subject to
$\| Ax - b \|_{2} \leq \delta$
and related forms, right?
There are many different applications in which problems are formulated as the minimization of the 1-norm of a vector subject to linear or least squares constraints.
An important area of theoretical research is proving conditions under which solving the $L_{1}$ minimization problem will recover the sparsest solution.
Many folks working in convex optimization have gravitated to this area because of the new found demand for solvers for these problems. The methods that they develop can be used in many different applications, and the solvers are effectively black boxes to most users of the codes.
It isn't clear whether you're more interested in the application of sparse optimization to machine learning or in theoretical questions or in methods for actually solving the resulting optimization problems. These are really very disjoint though related areas of research.
As a starting point, I'd suggest looking at the list of resources for compressive sensing at:
If you can supply more details about what it is you want to learn about, and also give me some idea of your background in optimization and other areas of mathematics, then perhaps I could suggest more specific references.
answered Aug 1, 2013 at 23:25
-
$\begingroup$ I'd love to find a text (one meant for teaching students, not research papers) that deals with the necessary conditions on $A$, $x$, and $b$ in order for $\ell_1$ to arrive at the correct solution. I've been reading Mallet's wavelet book but am not liking it at all (poorly written, non-standard notation, not well organized for self-learning about sparse $\ell_1$ minimization, along with other problems). Something at the graduate or advanced undergraduate level would be ideal. $\endgroup$ Commented Aug 17, 2013 at 10:32
-
1$\begingroup$ There are lots of sufficient conditions under which $L_{1}$ minimization will lead (with very high probability) to the sparse solution. You might find Elad's textbook on sparse and redundant representations helpful: amazon.com/… $\endgroup$ Commented Aug 17, 2013 at 17:39
$\begingroup$
$\endgroup$
1
It sounds like you're interested in iterative method in optimizing solution for a sparse system. If so, you can consult the following book:
-
1$\begingroup$ Actually, this isn't what the OP is looking for. Rather, the original poster is asking about algorithms for solving problems of the form $\min \| x \|_{1}$ subject to $\| Ax - b \|_{2} \leq \delta$ or related problems that commonly arise in compressive sensing. $\endgroup$ Commented Aug 1, 2013 at 23:10