|
|
|
“Maximally Sparse Constrained Optimization for Signal Processing Applications”
by Brian Dean Jeffs
January 1989
A new approach for vector space optimization is presented which enables solution of a number of signal processing problems, otherwise solvable only in a suboptimal sense. The method seeks a maximally sparse solution vector to a system of linear or quadratic inequality constraints. An optimal solution (typically not unique) contains the fewest possible nonzero terms consistent with the constraints. The relationship between lp quasinorm minimization and sparse optimization is discussed, and it is proved that for some p, 0 < p < 1, the constrained lp minimum will be maximally sparse. The related l 1|q cost function is shown to be a superior objective functional for deterministic sparse optimization, and to yield maximum a-posterior estimates when random sources are distributed as generalized p-Gaussian.
Three new algorithms based on the l 1|q cost are presented. The l 1|q simplex search algorithm achieves strong local optimality by searching the set of vertices of the convex polytope formed by linear constraints. The "basic" solutions corresponding to these vertices are proved to include the optimum. The stochastic search algorithm finds globally optimum results using techniques of simulated annealing to direct the simplex search. The convex transformation gradient search finds strong local optima of the quadratically constrained problem by transformation to a space where gradient search techniques are more successful.
Three applications are presented as examples of problems best solved using the maximally sparse criterion. Neuromagnetic image reconstruction produces 3-D maps of brain neural currents by reconstruction from externally measured induced magnetic fields. Sparse optimization is shown to be superior to other reconstruction methods which obscure virtually all current dipole position detail. Seismic deconvolution of sparse reflectivity sequences is demonstrated using all three of the algorithms, and design of thinned beamforming arrays using the stochastic search algorithm is shown to yield great improvement over existing methods. The new algorithms provide the only available method for thinning of arbitrarily shaped arrays in an optimal sense.