Seminar Details
2016-10-04 (14:00) : Semidefinite programming relaxations for matrix completion, inverse scattering and blind deconvolution
At Euler building (A002)
Organized by Mathematical Engineering
Speaker :
Augustin Cosse (UCL)
Abstract :
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 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 impulse response and input signals, through the Orlicz version of the Bernstein concentration bound.