The standard least-squares 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 componentwise magnitude of which approximates a target, is not a convex problem, but can be well-approximated 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.
展开▼
