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

The thesis studies semidefinite programming relaxations for three instances of the general affine rank minimization problem. The first instance, rank one matrix completion, was known to be solved by non-linear propagation algorithms without stability guarantees. The thesis closes the line of work on this problem by introducing a stable algorithm based on two levels of semidefinite programming relaxation. For this algorithm, recovery of the unknown matrix is first certified 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. For the second instance, inverse scattering, the thesis introduces a fast algorithm which leverages the traditional Adjoint State method 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 show 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, the thesis studies nuclear norm relaxation for the blind deconvolution problem when multiple input signals are considered. 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. ​