Helsinki Algorithms Seminar: "An Algebraic Approach to Rank-Constrained Semi-Definite Programs with Sum-of-Squares Constraints" Sergiy Vorobyov
Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design
Map © OpenStreetMap. Some rights reserved.
Speaker:
Sergiy Vorobyov
Title:
An Algebraic Approach to Rank-Constrained Semi-Definite Programs with Sum-of-Squares Constraints
Abstract:
A new approach to solving rank constrained semi-definite programming (SDP) problems with sum-of-squares (SOS) constraints will be presented. The essence of the approach is the use of underlying algebraic structure enforced by the SOS constraint, and instead of relaxing the non-convex rank constrained SDP problem to a feasible set of positive semidefinite matrices, restrict it to a space of polynomials whose dimension is equal to the desired rank. The resulting optimization problem is then convex as its solution is required to be full rank, and can be efficiently and exactly solved. A simple matrix decomposition is needed to recover the solution of the original non-convex NP-hard problem from the solution of the restricted one. We demonstrate how this approach can be applied to solving some important signal processing problems that contain SOS constraints corresponding to practical null-shaping constraints. Examples of such problems are transmit beamspace design in multiple-input multiple-output (MIMO) radar, downlink beamforming design in MIMO communications, generalized sidelobe canceller design. Among other related problems is the phase retrieval problem, but it does not have the exact algebraic structure corresponding to SOS. If time permits, it will be also discussed.
**
Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.
Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.
For the season programme, please see the seminar webpage.