In this paper we demonstrate that global photometric bundle adjustment (PBA) over all past keyframes can significantly improve the global accuracy of a monocular SLAM map compared to geometric techniques such as pose-graph optimization or traditional (geometric) bundle adjustment. However, PBA is computationally expensive in runtime, and memory usage can be prohibitively high. In order to address this scalability issue, we formulate PBA as an approximate consensus program. Due to its decomposable structure, the problem can be solved with block coordinate descent in parallel across multiple independent workers, each having lower requirements on memory and computational resources. For improved accuracy and convergence, we propose a novel gauge aware consensus update. Our experiments on real-world data show an average error reduction of 62% compared to odometry and 33% compared to intermediate pose-graph optimization, and that compared to the central optimization on a single machine, our distributed PBA achieves competitive pose-accuracy and cost.

Structured convex optimization on weighted graphs finds numerous applications in machine learning and computer vision. In this work, we propose a novel adaptive preconditioning strategy for proximal algorithms on this problem class. Our preconditioner is driven by a sharp analysis of the local linear convergence rate depending on the "active set" at the current iterate. We show that nested-forest decomposition of the inactive edges yields a guaranteed local linear convergence rate. Further, we propose a practical greedy heuristic which realizes such nested decompositions and show in several numerical experiments that our reconditioning strategy, when applied to proximal gradient or primal-dual hybrid gradient algorithm, achieves competitive performances. Our results suggest that local convergence analysis can serve as a guideline for selecting variable metrics in proximal algorithms.

In this work, we consider nonconvex composite problems that involve inf-convolution with a Legendre function, which gives rise to an anisotropic generalization of the proximal mapping and Moreau-envelope. In a convex setting such problems can be solved via alternating minimization of a splitting formulation, where the consensus constraint is penalized with a Legendre function. In contrast, for nonconvex models it is in general unclear that this approach yields stationary points to the infimal convolution problem. To this end we analytically investigate local regularity properties of the Moreau-envelope function under prox-regularity, which allows us to establish the equivalence between stationary points of the splitting model and the original inf-convolution model. We apply our theory to characterize stationary points of the penalty objective, which is minimized by the elastic averaging SGD (EASGD) method for distributed training, showing that perfect consensus between the workers is attainable via a finite penalty parameter. Numerically, we demonstrate the practical relevance of the proposed approach on the important task of distributed training of deep neural networks.

Photometric stereo (PS) techniques nowadays remain constrained to an ideal laboratory setup where modeling and calibration of lighting is amenable. To eliminate such restrictions, we propose an efficient principled variational approach to uncalibrated PS under general illumination. To this end, the Lambertian reflectance model is approximated through a spherical harmonic expansion, which preserves the spatial invariance of the lighting. The joint recovery of shape, reflectance and illumination is then formulated as a single variational problem. There the shape estimation is carried out directly in terms of the underlying perspective depth map, thus implicitly ensuring integrability and bypassing the need for a subsequent normal integration. To tackle the resulting nonconvex problem numerically, we undertake a two-phase procedure to initialize a balloon-like perspective depth map, followed by a “lagged” block coordinate descent scheme. The experiments validate efficiency and robustness of this approach. Across a variety of evaluations, we are able to reduce the mean angular error consistently by a factor of 2-3 compared to the state-of-the-art.

We tackle highly nonconvex, nonsmooth composite optimization problems whose objectives comprise a Moreau-Yosida regularized term. Classical nonconvex proximal splitting algorithms, such as nonconvex ADMM, suffer from lack of convergence for such a problem class. To overcome this difficulty, in this work we consider a lifted variant of the Moreau-Yosida regularized model and propose a novel multiblock primal-dual algorithm that intrinsically stabilizes the dual block. We provide a complete convergence analysis of our algorithm and identify respective optimality qualifications under which stationarity of the original model is retrieved at convergence. Numerically, we demonstrate the relevance of Moreau-Yosida regularized models and the efficiency of our algorithm on robust regression as well as joint feature selection and semi-supervised learning.

We present a novel preconditioning technique for proximal optimization methods that relies on graph algorithms to construct effective preconditioners. Such combinatorial preconditioners arise from partitioning the graph into forests. We prove that certain decompositions lead to a theoretically optimal condition number. We also show how ideal decompositions can be realized using matroid partitioning and propose efficient greedy variants thereof for large-scale problems. Coupled with specialized solvers for the resulting scaled proximal subproblems, the preconditioned algorithm achieves competitive performance in machine learning and vision applications.

This paper tackles the photometric stereo problem in the presence of inaccurate lighting, obtained either by calibration or by an uncalibrated photometric stereo method. Based on a precise modeling of noise and outliers, a robust variational approach is introduced. It explicitly accounts for self-shadows, and enforces robustness to cast-shadows and specularities by resorting to redescending M-estimators. The resulting non-convex model is solved by means of a computationally efficient alternating reweighted least-squares algorithm. Since it implicitly enforces integrability, the new variational approach can refine both the intensities and the directions of the lighting.

Recently, nonconvex regularization models have been introduced in order to provide a better prior for gradient distributions in real images. They are based on using concave energies $\phi$ in the total variation--type functional ${TV}^\phi(u) := \int \phi(|\nabla u(x)|)\,d x$. In this paper, it is demonstrated that for typical choices of $\phi$, functionals of this type pose several difficulties when extended to the entire space of functions of bounded variation, ${BV}(\Omega)$. In particular, if $\phi(t)=t^q$ for $q \in (0, 1)$, and ${TV}^\phi$ is defined directly for piecewise constant functions and extended via weak* lower semicontinuous envelopes to ${BV}(\Omega)$, then it still holds that ${TV}^\phi(u)=\infty$ for $u$ not piecewise constant. If, on the other hand, ${TV}^\phi$ is defined analogously via continuously differentiable functions, then ${TV}^\phi \equiv 0$ (!). We study a way to remedy the models through additional multiscale regularization and area strict convergence, provided that the energy $\phi(t)=t^q$ is linearized for high values. The fact that such energies actually better match reality and improve reconstructions is demonstrated by statistics and numerical experiments.

A nonconvex variational model is introduced which contains the $\ell_q$-``norm,” $q\in (0,1)$, of the gradient of the underlying image in the regularization part together with a least squares--type data fidelity term which may depend on a possibly spatially dependent weighting parameter. Hence, the regularization term in this functional is a nonconvex compromise between the minimization of the support of the reconstruction and the classical convex total variation model. In the discrete setting, existence of a minimizer is proved, and a Newton-type solution algorithm is introduced and its global as well as local superlinear convergence toward a stationary point of a locally regularized version of the problem is established. The potential nonpositive definiteness of the Hessian of the objective during the iteration is handled by a trust-region--based regularization scheme. The performance of the new algorithm is studied by means of a series of numerical tests. For the associated infinite dimensional model an existence result based on the weakly lower semicontinuous envelope is established, and its relation to the original problem is discussed.