Optimization Algorithms for Sparse Representations and Applications

Abstract

We consider the following sparse representation problem, which is called Sparse Component Analysis: identify the matrices S ∈ IRn×N and A ∈ IRm×n (m ≤ n < N) uniquely (up to permutation of scaling), knowing only their multiplication X = AS, under some conditions, expressed either in terms of A and sparsity of S (identifiability conditions), or in terms of X (Sparse Component Analysis conditions). A crucial assumption (sparsity condition) is that S is sparse of level k in sense that each column of S has at most k nonzero elements (k = 1,2, ..., m − 1).
We present two type of optimization problems for such identification. The first one is used for identifying the mixing matrix A: this is a typical clustering type problem aimed to finding hyperplanes in IRm which contain the columns of X. We present a general algorithm for this clustering problem and a modification of Bradley-Mangasarian’s k-planes clustering algorithm for data allowing reduction of this problem to an orthogonal one.
The second type of problems is those of identifying the source matrix S. This corresponds to finding a sparse solution of a linear system. We present a source recovery algorithm, which allows to treat underdetermined case.
Applications include Blind Signal Separation of under-determined linear mixtures of signals in which the sparsity is either given a priori, or obtained with some preprocessing techniques as wavelets, filtering, etc. We apply our orthogonal m-planes clustering algorithm to fMRI analysis.