上海科技大学知识管理系统

This paper considers blind deconvolution problem that to recover unknown signals f and 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.