Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
This is an incremental review paper summarizing existing theory and methods for a problem relevant to signal processing and machine learning researchers.
The paper reviews recent advances in global nonconvex optimization theory for finding the sparsest vector in a subspace, addressing applications in robust subspace recovery, dictionary learning, and sparse blind deconvolution, but does not report specific numerical results or SOTA improvements.
The problem of finding the sparsest vector (direction) in a low dimensional subspace can be considered as a homogeneous variant of the sparse recovery problem, which finds applications in robust subspace recovery, dictionary learning, sparse blind deconvolution, and many other problems in signal processing and machine learning. However, in contrast to the classical sparse recovery problem, the most natural formulation for finding the sparsest vector in a subspace is usually nonconvex. In this paper, we overview recent advances on global nonconvex optimization theory for solving this problem, ranging from geometric analysis of its optimization landscapes, to efficient optimization algorithms for solving the associated nonconvex optimization problem, to applications in machine intelligence, representation learning, and imaging sciences. Finally, we conclude this review by pointing out several interesting open problems for future research.