Blind deconvolution by Optimizing over a Quotient Manifold

4:30PM at UNIV 103
Dr. Wen Huang, Rice University
Blind deconvolution by Optimizing over a Quotient Manifold

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.