Low-rank structure in semidefinite programming and sum-of-squares optimization in signal processing

Semidefinite programming is an extension of linear programming in which the linear inequality constraints are replaced by the linear matrix inequalities. Semidefinite programs can be solved by interior-point methods that extend interior-point methods for linear programming and have a similar worst-case complexity. Since the 1990s, numerous applications of semidefinite programming have been discovered in control, signal processing, machine learning, combinatorial optimization, and other areas. Several high-quality general-purpose solver packages have also been developed.; Much of the recent work in this field has centered around optimization problems involving nonnegative polynomial constraints. The basic observation is that sum-of-squares formulations (or relaxations) of such problems can be solved by semidefinite programming. In practice, however, the semidefinite programs that result from this approach are often challenging for general-purpose solvers due to the presence of large auxiliary matrix variables. It is therefore of interest to develop specialized algorithms for semidefinite programs derived from sum-of-squares formulations.; In this thesis it is shown that a substantial reduction in the complexity can be achieved by exploiting problem structure. A fast method is presented, based on reformulating the sum-of-squares constraints using discrete transforms. This leads to semidefinite programs with a low-rank structure that is easily exploited in interior-point algorithms. For optimization problems involving trigonometric polynomials the idea can be implemented in a fast and stable way via the discrete Fourier transform. The advantages of this approach are demonstrated with examples of one- and two-dimensional filter design problems.