An Efficient Method for Non-Convex Blind Deconvolution

This paper considers blind deconvolution problem that to recover unknown signals fand g from their convolution signal. Non-convex optimization approach is an efficient method to get the solution, but it is a challenge to find the exact solution for a non-convex optimization problem. Existing work provides a full gradient descent (GD) method converging to the global minimum from a proper initialization. However, GD algorithm is not computationally efficient. In this paper, we design the first stochastic gradient descent (SGD) algorithm that converges linearly to the exact solution. We also design a Kaczmarz algorithm which adapts the step size of SGD algorithm. It also has the linear convergence and is more computationally efficient. Finally, we analyze the global geometry of the objective function. Although the function is non-convex, its expectation has a good geometry that every local minimum is also a global optimal point. Our numerical experiments demonstrate that both SGD and Kaczmarz algorithms are more computationally efficient and can converge to the global minimum even without a proper initialization.

Abstract licence: CC BY-NC-ND

40 more references, whose wording the paper’s licence keeps private.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.