Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems

By Raja Giryes, Yonina C. Eldar, A. Bronstein, Guillermo Sapiro. 2016

86 citations recorded by the source corpus.

Solving inverse problems with iterative algorithms is popular, especially for large data. Due to time constraints, the number of possible iterations is usually limited, potentially affecting the achievable accuracy. Given an error one is willing to tolerate, an important question is whether it is possible to modify the original iterations to obtain faster convergence to a minimizer achieving the allowed error without increasing the computational cost of each iteration considerably. Relying on recent recovery techniques developed for settings in which the desired signal belongs to some low-dimensional set, we show that using a coarse estimate of this set may lead to faster convergence at the cost of an additional reconstruction error related to the accuracy of the set approximation. Our theory ties to recent advances in sparse recovery, compressed sensing, and deep learning. Particularly, it may provide a possible explanation to the successful approximation of the $\ell _1$ -minimization solution by neural networks with layers representing iterations, as practiced in the learned iterative shrinkage-thresholding algorithm.

Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Robust Large Margin Deep Neural Networks (2016, background): “The role of DNNs in improving convergence speed of various iterative algorithms is studied in [19].”
Learning to Optimize: A Primer and A Benchmark (2021, background): “Most of unrolling works following [75] also solve LASSO-type optimization problems for sparse coding [190; 161; 171; 72; 262; 4; 78; 59; 232].”
Convolutional Neural Networks Analyzed via Convolutional Sparse Coding (2016, background): “Later, (Giryes et al., 2016) proved the theoretical justification for this algorithm, and (Sprechmann et al.”
Mathematics of Deep Learning (2017, background): “As random projection is a universal sampling strategy for low-dimensional data [59], [60], [61], deep networks with random weights are a universal system that separates any data (belonging to a low-dimensional model) according to the angles between the data points, where the general assumption is…”
Solving inverse problems using data-driven models (2019, methodology): “Other applications of the learned gradient method include those of Gong et al. (2018) for deconvolution, Qin et al.”