Optimization Algorithms for Sparse Representations and Applications
Pando Georgiev, Fabian Joachim Theis, Andrzej S Cichocki · Kluwer Academic Publishers eBooks · 2006
SummaryWe 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.