The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-SIPI-131

“Maximally Sparse Optimization for Array Beamforming and Other Applications”

by Brian Jeffs and Richard Leahy

September 1988

In this paper we introduce algorithms for finding optimally sparse solutions subject to linear and quadratic constraints. The problem of finding the maximally sparse solution, i.e. the vector with fewest non-zero terms, is shown to be closely related to l p optimization for 0 < p < 1. For linearly constrained problems, it is non linear simplex algorithm is presented for efficiently locating a local minimum on the connected graph of basic feasible solutions. By modifying the algorithm to include a stochastic search, it is shown that a global minimum of the problem may be found. For quadratic constraints, the maximally sparse solution is found by means of a convex transformation. The utility of these algorithms is demonstrated in the design of arbitrarily shaped, narrowband beamforming arrays. Using the maximally sparse criteria we are able to perform optimal array thinning and element placement for this problem for an arbitrary set of linear response constraints. The algorithms also have many other applications in signal processing, one such application considered in this paper is the recovery of sparse reflectivity sequences in seismic deconvolution.

To download the report in PDF format click here: USC-SIPI-131.pdf (2.2Mb)