Abstract. We present the Multilevel Bregman Proximal Gradient Descent (ML-BPGD) method, a novel multilevel optimization framework tailored to constrained convex problems with relative Lipschitz smoothness. Our approach extends the classical multilevel optimization framework (MGOPT) to Bregman-based geometries and constrained domains. We provide a rigorous analysis of ML-BPGD for multiple levels and establish well-posedness together with a global linear convergence rate. We demonstrate the effectiveness of ML-BPGD in the context of image reconstruction and validate its performance through numerical experiments.

This paper extends the recently introduced assignment flow approach for supervised image labeling to unsupervised scenarios where no labels are given. The resulting self-assignment flow takes a pairwise data affinity matrix as input data and maximizes the correlation with a low-rank matrix that is parametrized by the variables of the assignment flow, which entails an assignment of the data to themselves through the formation of latent labels (feature prototypes). A single user parameter, the neighborhood size for the geometric regularization of assignments, drives the entire process. By smooth geodesic interpolation between different normalizations of self-assignment matrices on the positive definite matrix manifold, a one-parameter family of self-assignment flows is defined. Accordingly, our approach can be characterized from different viewpoints, e.g., as performing spatially regularized, rank-constrained discrete optimal transport, or as computing spatially regularized normalized spectral cuts. Regarding combinatorial optimization, our approach successfully determines completely positive factorizations of self-assignments in large-scale scenarios, subject to spatial regularization. Various experiments, including the unsupervised learning of patch dictionaries using a locally invariant distance function, illustrate the properties of the approach.

We study unique recovery of cosparse signals from limited-view tomographic measurements of two- and three-dimensional domains. Admissible signals belong to the union of subspaces defined by all cosupports of maximal cardinality ℓ with respect to the discrete gradient operator. We relate ℓ both to the number of measurements and to a nullspace condition with respect to the measurement matrix, so as to achieve unique recovery by linear programming. These results are supported by comprehensive numerical experiments that show a high correlation of performance in practice and theoretical predictions. Despite poor properties of the measurement matrix from the viewpoint of compressed sensing, the class of uniquely recoverable signals basically seems large enough to cover practical applications, like contactless quality inspection of compound solid bodies composed of few materials.

We analyze representative ill-posed scenarios of tomographic PIV (particle image velocimetry) with a focus on conditions for unique volume reconstruction. Based on sparse random seedings of a region of interest with small particles, the corresponding systems of linear projection equations are probabilistically analyzed in order to determine: (i) the ability of unique reconstruction in terms of the imaging geometry and the critical sparsity parameter, and (ii) sharpness of the transition to non-unique reconstruction with ghost particles when choosing the sparsity parameter improperly. The sparsity parameter directly relates to the seeding density used for PIV in experimental fluids dynamics that is chosen empirically to date. Our results provide a basic mathematical characterization of the PIV volume reconstruction problem that is an essential prerequisite for any algorithm used to actually compute the reconstruction. Moreover, we connect the sparse volume function reconstruction problem from few tomographic projections to major developments in compressed sensing.

A variational approach is presented to the estimation of turbulent fluid flow from particle image sequences in experimental fluid mechanics. The approach comprises two coupled optimizations for adapting size and shape of a Gaussian correlation window at each location and for estimating the flow, respectively. The method copes with a wide range of particle densities and image noise levels without any data-specific parameter tuning. Based on a careful implementation of a multiscale nonlinear optimization technique, we demonstrate robustness of the solution over typical experimental scenarios and highest estimation accuracy for an international benchmark data set (PIV Challenge).

In the above paper (ibid., vol. 21, no. 6, pp. 3053-3065, Jun. 2012), several corrections requested by the authors were omitted. The IEEE regrets the error. On pp. 3058 and 3059, the algorithms were not indented corrected. They are corrected here.