Sparse Optimization: Algorithms and Applications
Many signal- and image-processing applications seek sparse solutions to large underdetermined linear systems. The basis-pursuit approach minimizes the 1-norm of the solution, and the basis-pursuit denoising approach balances it against the least-squares fit. The resulting problems can be recast as conventional linear and quadratic programs. Useful generalizations of 1-norm regularization, however, involve optimization over matrices, and often lead to considerably more difficult problems. Two recent examples: problems with multiple right-hand sides require joint-sparsity patterns among the solutions and involve minimizing the sum of row norms; matrix-completion problems require low-rank matrix approximations, and involve minimizing the sum of singular values. I will survey some of the most successful and promising approaches for sparse optimization, and will show examples from a variety of applications.
Michael Friedlander, University of British Columbia,
