Sparse Recovery via l1 and L1 Optimization
Abstract
A sparse signal is a signal that has very few nonzero elements or one that becomes so under a basis change or through a certain transform. Exploiting sparsity has become a common task in data sciences. Compressed sensing, regularized regression (e.g., LASSO), and regularized inverse problems (e.g., total variation image reconstruction) have made l1 optimization a central tool in data processing problems. As the name suggests, l1 optimization problems recover sparse solutions by solving an optimization problem involving an l1-norm. Today, the scope of l1 optimization is quickly expanding. The size, complexity, and diversity of instances have grown significantly. Beyond 1D signals and 2D images, high-dimensional quantities such as video, 4D CT, and multi-way tensors have become the data or unknown variables in models. New applications have motivated structured solutions to optimization problems that significantly generalize our notion of sparsity. Such applications look for low-rank matrices or tensors, sparse graphs, tree structured data representations, and sparse representations involving only a few dictionary atoms. This article gives self-contained introductions to l1 optimization for sparse vectors (Section 2), L1 optimization for finding functions with compact support (Section 3), and computing sparse solutions from measurements that are corrupted by unknown noisy (Section 4).
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 2014
- Accession Number
- ADA613294
Entities
People
- Stanley Osher
- Wotao Yin
Organizations
- University of California, Los Angeles