Tensor-Free Proximal Methods for Lifted Bilinear/Quadratic Inverse Problems with Applications to Phase Retrieval

Robert Beinert, Kristian Bredies

TL;DR

This paper introduces novel "tensor-free" algorithms for solving complex inverse problems, specifically bilinear and quadratic ones like phase retrieval. By cleverly reformulating these problems and avoiding computationally expensive tensor operations, the authors achieve efficient and memory-saving solutions, even for high-dimensional data.

What Problem Does This Paper Address?

Many real-world problems in fields like medicine, engineering, and physics involve "inverse problems." These are tasks where we try to recover an underlying signal or image from incomplete or noisy measurements. Specifically, this paper focuses on bilinear and quadratic inverse problems, which are common in areas like deconvolution, blind source separation, and phase retrieval (recovering a signal from its intensity measurements, which lose phase information).

A common approach to tackle these problems is through "tensorial lifting," which transforms them into linear problems on a much larger "tensor product space." While this allows for standard optimization techniques, the sheer size of this space makes direct computation intractable for many applications, especially with image data. The challenge is to solve these lifted problems efficiently without the computational burden of explicitly working with these massive tensor spaces.

Methods

The core of the paper's contribution lies in developing "tensor-free" algorithms. The authors start by reformulating bilinear and quadratic inverse problems into linear problems on a tensor product space, then relax the non-convex rank-one constraint using nuclear or projective norms. This leads to convex minimization problems that can be solved with proximal first-order methods, like the primal-dual method.

The key innovation is the "tensor-free" aspect. Instead of performing operations on the full, enormous tensor product space, they derive equivalent operations that only require left- and right-hand actions of the tensor. This is achieved by leveraging low-rank representations and techniques like subspace iteration and Lanczos bidiagonalization. These methods allow for the computation of singular value decompositions (or eigenvalue decompositions for quadratic problems) without explicitly forming the full tensor.

Furthermore, the paper introduces a novel "reweighting technique" to promote lower-rank solutions and improve convergence. This technique modifies the inner product norms of the underlying Hilbert spaces to favor specific directions, effectively guiding the iterative process towards sparser solutions.

Datasets

The paper uses synthetic data generated from a real-world TEM (transmission electron microscopy) reconstruction of nanoparticles. This data is used to demonstrate the effectiveness of the proposed algorithms for the masked Fourier phase retrieval problem. The authors specifically mention using a 16x16 pixel image for initial experiments and then scaling up to a 1024x1024 pixel image for large-scale demonstrations.

Key Insights and Ideas

  • Tensor-Free is the Key: The most significant insight is that it's possible to solve complex inverse problems that are formulated on huge tensor product spaces without ever explicitly constructing those spaces. This is a major computational breakthrough.
  • Low-Rank is Natural: The relaxation of the rank-one constraint using nuclear/projective norms naturally promotes low-rank solutions. This is a crucial observation that enables the tensor-free approach.
  • Reweighting for Better Rank Reduction: The proposed reweighting technique is not just about promoting low rank; it actively reduces the rank of the iterates, leading to faster convergence and more accurate reconstructions, especially in challenging scenarios like phase retrieval.
  • Flexibility for Domain Knowledge: The framework allows for incorporating a-priori information about the signal (like smoothness) by modifying the Hilbert space norms. This is a powerful feature for improving reconstruction quality.

Key Results

The paper demonstrates that their tensor-free proximal algorithms are efficient and memory-saving, significantly outperforming direct tensor-based methods. For instance, a reconstruction task that took 6.38 minutes with a direct method was reduced to about 58 seconds using the tensor-free approach with augmented Lanczos bidiagonalization.

The reweighting technique was shown to effectively reduce the rank of the iterates, often achieving rank-one solutions, which is crucial for phase retrieval. The algorithms also showed stability under noise and the ability to recover pixels not covered by masks when incorporating smoothness priors.

Limitations and Future Work

  • Convergence Analysis for Reweighting: The authors note that they are not aware of a convergence and error analysis for the specific variant of the augmented Lanczos method used with reweighting.
  • Generalizing Norms: The paper mentions that while they use projective norms based on Hilbert norms, the question of whether nuclear "norms" based on semi-norms (like total variation) could be employed remains open.
  • Noise Models: The current work primarily addresses white or Gaussian noise. The authors suggest that incorporating more realistic noise models, such as Poisson noise, could be achieved by adapting the data fidelity term and proximal mapping.
  • Parameter Selection: While the algorithms are shown to be effective, the paper acknowledges that more sophisticated parameter choice rules could further improve results, especially in noisy scenarios.

Summary updated

Abstract

We propose and study a class of novel algorithms that aim at solving bilinear and quadratic inverse problems. Using a convex relaxation based on tensorial lifting, and applying first-order proximal algorithms, these problems could be solved numerically by singular value thresholding methods. However, a direct realization of these algorithms for, e.g., image recovery problems is often impracticable, since computations have to be performed on the tensor-product space, whose dimension is usually tremendous. To overcome this limitation, we derive tensor-free versions of common singular value thresholding methods by exploiting low-rank representations and incorporating an augmented Lanczos process. Using a novel reweighting technique, we further improve the convergence behavior and rank evolution of the iterative algorithms. Applying the method to the two-dimensional masked Fourier phase retrieval problem, we obtain an efficient recovery method. Moreover, the tensor-free algorithms are flexible enough to incorporate a-priori smoothness constraints that greatly improve the recovery results.
BibTeX
@article{beinert2021tensor,
  author = {Robert Beinert and Kristian Bredies},
  title = {{Tensor-Free Proximal Methods for Lifted Bilinear/Quadratic Inverse Problems with Applications to Phase Retrieval}},
  journal = {Found. Comput. Math},
  year = {2021},
  doi = {10.1007/s10208-020-09479-4},
}
Figure