A fast method for sparse component analysis based on iterative detection-projection

Abstract. We introduce a new iterative algorithm for Sparse Component Analysis (SCA). The algorithm, which we call Iterative Detection-Estimation (IDE), is essentially a method to find sufficiently sparse solutions of underdetermined linear systems of equations. In the SCA context, this solves the source separation part of the problem. Each iteration of IDE consists of two steps. In the detection step, starting with a previously known estimate of the sparse solution vector, we detect which components of the solution are (possibly) active, i.e., having a considerable value. Then, in the estimation step, we compute the new estimate by finding a solution of the system which is the closest to the subspace specified by the detection step. This is called projection into the activity subspace. We will compare the solution obtained by the proposed algorithm against the minimum 1-norm solution obtained by Linear Programming (LP). It is shown by experiment that, with proper choice of parameters, the proposed algorithm is about two orders of magnitude faster than state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy. The algorithm may then be considered as an alternative to the LP approach for large-scale problems