Optimal Sample Complexity of Subgradient Descent for Amplitude Flow via Non-Lipschitz Matrix Concentration
This provides an optimal sample complexity guarantee for a traditional inverse problem in signal recovery, though it is incremental in extending existing concentration techniques to non-Lipschitz settings.
The paper tackles the problem of recovering a real-valued signal from phaseless linear measurements by analyzing subgradient descent on a non-smooth objective, establishing local convergence with optimal sample complexity of m = Ω(n) for Gaussian measurements. It proves that a discontinuous matrix-valued operator satisfies uniform concentration, enabling linear convergence to the true solution up to sign ambiguity.
We consider the problem of recovering a real-valued $n$-dimensional signal from $m$ phaseless, linear measurements and analyze the amplitude-based non-smooth least squares objective. We establish local convergence of subgradient descent with optimal sample complexity based on the uniform concentration of a random, discontinuous matrix-valued operator arising from the objective's gradient dynamics. While common techniques to establish uniform concentration of random functions exploit Lipschitz continuity, we prove that the discontinuous matrix-valued operator satisfies a uniform matrix concentration inequality when the measurement vectors are Gaussian as soon as $m = Ω(n)$ with high probability. We then show that satisfaction of this inequality is sufficient for subgradient descent with proper initialization to converge linearly to the true solution up to the global sign ambiguity. As a consequence, this guarantees local convergence for Gaussian measurements at optimal sample complexity. The concentration methods in the present work have previously been used to establish recovery guarantees for a variety of inverse problems under generative neural network priors. This paper demonstrates the applicability of these techniques to more traditional inverse problems and serves as a pedagogical introduction to those results.