Many algorithms for high-dimensional regression problems require the calibration of regularization hyperparameters. This, in turn, often requires the knowledge of the unknown noise variance in order to produce meaningful solutions. Recent works show, however, that there exist certain estimators that are pivotal, i.e., the regularization parameter does not depend on the noise level; the most remarkable example being the square-root lasso. Such estimators have also been shown to exhibit strong connections to distributionally robust optimization. Despite the progress in the design of pivotal estimators, the resulting minimization problem is challenging as both the loss function and the regularization term are non-smooth. To date, the design of fast, robust, and scalable algorithms with strong convergence rate guarantees is still an open problem. This work addresses this problem by showing that an iteratively reweighted least squares (IRLS) algorithm exhibits global linear convergence under the weakest assumption available in the literature. We expect our findings will also have implications for multi-task learning and distributionally robust optimization.

Abstract. Ptychography is a computational imaging technique that aims to reconstruct the object of interest from a set of diffraction patterns. Each of these is obtained by a localized illumination of the object, which is shifted after each illumination to cover its whole domain. Because in the resulting measurements the phase information is lost, ptychography gives rise to solving a phase retrieval problem. In this work, we consider ptychographic measurements contaminated by a background signal. Such a background is caused by imperfections in the experimental setup and appears as a signal that is added to the diffraction patterns. The background is assumed to be independent of the shift of the object, i.e., it is the same for all diffraction patterns. Two algorithms are provided, for arbitrary objects and for so-called phase objects that do not absorb the light but only scatter it. For the second type, a uniqueness of reconstruction is established for almost every object. Our approach is based on the Wigner distribution deconvolution, which lifts the object to a higher-dimensional matrix space where the recovery can be reformulated as a linear problem. The background only affects a few equations of the linear system that are therefore discarded. The lost information is then restored using redundancy in the higher-dimensional space.

Abstract. Ptychography is a lensless imaging technique, which considers reconstruction from a set of far-field diffraction patterns obtained by illuminating small overlapping regions of the specimen. In many cases, the distribution of light inside the illuminated region is unknown and has to be estimated along with the object of interest. This problem is referred to as blind ptychography. While in ptychography the illumination is commonly assumed to have a point spectrum, in this paper we consider an alternative scenario with a nontrivial light spectrum known as blind polychromatic ptychography. First, we show that nonblind polychromatic ptychography can be seen as a recovery from quadratic measurements. Then, a reconstruction from such measurements can be performed by a variant of the Amplitude Flow algorithm, which has guaranteed sublinear convergence to a critical point. Second, we address recovery from blind polychromatic ptychographic measurements by devising an alternating minimization version of Amplitude Flow and showing that it converges to a critical point at a sublinear rate.