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.

In this paper, we propose mathematical models for reconstructing the optical flow in time-harmonic elastography. In this image acquisition technique, the object undergoes a special time-harmonic oscillation with known frequency so that only the spatially varying amplitude of the velocity field has to be determined. This allows for a simpler multi-frame optical flow analysis using Fourier analytic tools in time. We propose three variational optical flow models and show how their minimization can be tackled via Fourier transform in time. Numerical examples with synthetic as well as real-world data demonstrate the benefits of our approach.

Keywords: optical flow, elastography, Fourier transform, iteratively reweighted least squares, Horn–Schunck method

High-dimensional real-world systems can often be well characterized by a small number of simultaneous low-complexity interactions. The analysis of variance (ANOVA) decomposition and the anchored decomposition are typical techniques to find sparse additive decompositions of functions. In this paper, we are interested in a setting, where these decompositions are not directly sparse, but become so after an appropriate basis transform. Noting that the sparsity of those additive function decompositions is equivalent to the fact that most of its mixed partial derivatives vanish, we can exploit a connection to the underlying function graphs to determine an orthogonal transform that realizes the appropriate basis change. This is done in three steps: we apply singular value decomposition to minimize the number of vertices of the function graph, and joint block diagonalization techniques of families of matrices followed by sparse minimization based on relaxations of the zero “norm” for minimizing the number of edges. For the latter one, we propose and analyze minimization techniques over the manifold of special orthogonal matrices. Various numerical examples illustrate the reliability of our approach for functions having, after a basis transform, a sparse additive decomposition into summands with at most two variables.

We consider blind ptychography, an imaging technique which aims to reconstruct an object of interest from a set of its diffraction patterns, each obtained by a local illumination. As the distribution of the light within the illuminated region, called the window, is unknown, it also has to be estimated as well. For the recovery, we consider gradient and stochastic gradient descent methods for the minimization of amplitude-base squared loss. In particular, this includes extended Ptychographic Iterative Engine as a special case of stochastic gradient descent. We show that all methods converge to a critical point at a sublinear rate with a proper choice of step sizes. We also discuss possibilities for larger step sizes.

We consider recovery from ptychographic measurements also known as Short-Time Fourier Transform phase retrieval. We study Amplitude Flow, Error Reduction and Ptychographic Iterative Engine algorithms and derive their convergence speed. In addition, Block Phase Retrieval algorithm and its modifications are studied. Furthermore, we consider blind ptychography and devise a version of Amplitude Flow with guaranteed convergence. Finally, some results are extended to polychromatic ptychography.