TitleMagnitude Least--Squares Fitting via Semidefinite Programming with Applications to Beamforming and Multidimensional Filter Design
Publication TypeConference Paper
Year of Publication2005
AuthorsKassakian, P
Conference NameIEEE International Conference on Acoustics, Speech, and Signal Processing
Conference LocationPhiladelphia, Pennsylvania

The standard leastsquares problem seeks to find a linear combination of columns of a given matrix that best approximates a target vector in Euclidean norm. The problem of finding a linear combination of columns, the component-wise magnitude of which approximates a target, is not a convex problem, but can be wellapproximated using semidefinite programming. High quality solutions can be found by reformulating the problem as a generalization of a graph partitioning problem, relaxing a rank constraint, and rounding back onto the feasible set. A bound on the gap between the objectives of the global optimum and the approximate solution can be calculated for instances of the problem, and for many practical problems can be quite small. The problem is shown to have application in array pattern synthesis, multidimensional filtering, and spectral factorization.