Harmonic Analysis and Signal Processing Seminar

Semidefinite programming relaxations for matrix completion, inverse scattering and blind deconvolution

Augustin Cosse
NYU CDS and Courant Institute

Wednesday, May 17, 2017, 2pm, WWH 1314


The talk will discuss three instances of semidefinite programming relaxation. In the first part, the talk will close the line of work on rank one matrix completion by introducing a stable algorithm based on two levels of semidefinite programming relaxation. For this algorithm, we first certify recovery of the matrix encoding the unknowns in the absence of noise, at the information limit, through the construction of a dual (sum of squares) polynomial. In passing, this dual polynomial also provides a rationale for the use of the trace norm in semidefinite programming. The dual polynomial is then used to derive a stability estimate for the noisy version of the problem. In the second part, we introduce a fast algorithm for inverse scattering which leverages the traditional Adjoint State method used in geophysics by lifting the search space. The algorithm is based on a first level of semidefinite programming relaxation encoded through a low rank factorization which guarantees its scalability. Numerical experiments on 2D community models are used to highlight a modest increase with respect to the basin of attraction of traditional least squares waveform inversion. A geometric intuition for this improvement is provided. Finally, in the last part of the talk, we discuss how blind deconvolution can be solved with high probability, in a stable way and in the case of a fully unknown filter, through nuclear norm relaxation, by considering multiple input signals. Recovery is certified through the construction of a dual certificate. A candidate certificate is first constructed through the golfing scheme. Relying on the recent line of work on blind deconvolution, this candidate certificate is then shown to satisfy the conditions from duality theory for the recovery of the rank one matrix encoding the filter and input signals, through the Orlicz version of the Bernstein concentration bound. (Joint work with Laurent Demanet)