|
|
|
“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.