Blind deconvolution by Optimizing over a Quotient Manifold (Wen Huang - Rice University)

28.11.2017 14:00 – 15:00

We consider the problem of separating two unknown signals given their circular convolution. We formulate this problem as a nonconvex optimization problem on a quotient manifold and propose Riemannian optimization algorithms for solving the problem. We prove that the proposed algorithm with an appropriate initialization will recover the exact solution with high probability when the number of measurements is, up to log-factors, the information-theoretical minimum scaling. The quotient structure in our formulation yields a simpler penalty term in the cost function compared to the Wirtinger gradient descent method, which eases the convergence analysis and yields a natural implementation. Empirically, the proposed algorithm has better performance than the Wirtinger gradient descent algorithm and an alternating minimization algorithm in the sense that i) it needs fewer operations, such as DFTs and matrix-vector multiplications, to reach a similar accuracy, and ii) it has a higher probability of successful recovery in synthetic tests.

This is joint work with Paul Hand at Rice university.

Lieu

Room 623, Séminaire d'analyse numérique

entrée libre