Nonlinear image reconstruction based upon sparse representations of signals and images has received widespread attention recently with the advent of compressed sensing. This emerging theory indicates that, when feasible, judicious selection of the type of distortion induced by measurement systems may lead to dramatically improved inverse problem solutions. In particular, when the signal or image of interest is very sparse (i.e., zero-valued at most locations) or highly compressible in some basis, relatively few indirect observations are necessary to reconstruct the most significant non-zero signal components. Compressed sensing theory states that sparse signals can be recovered very accurately with high probability from indirect measurements by solving an appropriate optimization problem. This research aims at the development of significantly more efficient methods for solving compressed sensing minimization problems. A crucial property of the proposed methods is that the algorithms are designed to be "matrix-free", i.e., they do not require the storage of (potentially very large) second-derivative matrices. Instead, these methods use matrices only as operators for matrix-vector products. This research also includes the application of the developed solvers to real large-scale problems from image processing (e.g., coded aperture superresolution, hyperspectral image reconstruction, and compressive video reconstruction), as well as theoretical proofs of convergence and numerical stability of the algorithms.
"Compressed sensing" is an emerging field in computational mathematics that aims to improve signal (and image) reconstruction with less data. More efficient methods for compressed sensing can benefit such fields as medical imaging, astrophysics, biosensing, and geophysical data analysis. The basic theory exploits the fact that many natural signals in science and engineering are "sparse"--that is, they can be represented as a weighted combination of a small subset of commonly occurring signals. When a signal is sparse, scientists can accurately reconstruct the original signal using a relatively small number of measurements of the original signal. However, in practice finding the right weighted combination of signals can create staggering numerical and computational complexity. This research aims to develop novel optimization methods that can quickly find accurate solutions to these large-scale problems. For example, consider an astronomer wishing to image the night sky, which consists of small, bright stars against a dark background. A conventional digital camera or imaging system would need a very high resolution and sensitive photodetector to effectively localize the different stars, but collecting this large number of pixels can be very costly and energy inefficient. This work allows the astronomer to collect a relatively small number of random projection measurements of the scene and use these to reconstruct the image with a high probability of accuracy. Fast and accurate optimization algorithms for sparse signal reconstruction can impact many other areas of image and signal processing as well, from reducing the dose of CT scans in biomedical imaging and improving image resolution in video surveillance systems for airport security, to more efficiently transmitting communication signals from distant satellites and NASA spacecraft and more carefully monitoring the health of a forest ecosystem using hyperspectral imaging.
"Compressed sensing" is an emerging field in computational mathematics that aims to improve signal (and image) reconstruction with less data. More efficient methods for compressed sensing can benefit such fields as medical imaging, astrophysics, biosensing, and geophysical data analysis. The basic theory exploits the fact that many natural signals in science and engineering are "sparse"–that is, they can be represented as a weighted combination of a small subset of commonly occurring signals. When a signal is sparse, scientists can accurately reconstruct the original signal using a relatively small number of measurements of the original signal. However, in practice finding the right weighted combination of signals can create staggering numerical and computational complexity. This research aims to develop novel optimization methods that can quickly find accurate solutions to these large-scale problems. For example, consider an astronomer wishing to image the night sky, which consists of small, bright stars against a dark background. A conventional digital camera or imaging system would need a very high resolution and sensitive photodetector to effectively localize the different stars, but collecting this large number of pixels can be very costly and energy inefficient. This work allows the astronomer to collect a relatively small number of random projection measurements of the scene and use these to reconstruct the image with a high probability of accuracy. Fast and accurate optimization algorithms for sparse signal reconstruction can impact many other areas of image and signal processing as well, from reducing the dose of CT scans in biomedical imaging and improving image resolution in video surveillance systems for airport security, to more efficiently transmitting communication signals from distant satellites and NASA spacecraft and more carefully monitoring the health of a forest ecosystem using hyperspectral imaging. The research outcomes of this grant include the following: Compressive coded apertures for practical imaging. While compressive sensing is a powerful theoretical tool for reducing the number of measurements needed to accurately capture scene information, applying this theory to practical imaging systems is challenging in the face of several measurement system constraints. We designed coded aperture masks for superresolution image reconstruction from a single, low-resolution, noisy observation image. Based upon recent theoretical work on Toeplitz- structured matrices for compressive sensing, the masks we developed are fast and memory-efficient to compute. In addition, we applied this technique to video compressed sensing applications. Poisson compressed sensing. The observations in many applications consist of counts of discrete events, such as photons hitting a detector, which cannot be effectively modeled using an additive bounded or Gaussian noise model, and instead require a Poisson noise model. As a result, accurate reconstruction of a spatially or temporally distributed phenomenon from Poisson data cannot be accomplished by minimizing a conventional CS objective function. The problem addressed in this work is the estimation of the true signal from the noise-corrupted data in an inverse problem setting, where (a) the number of unknowns may potentially be larger than the number of observations and (b) the true signal admits a sparse approximation in some basis. The optimization formulation considered in this work uses a negative Poisson log-likelihood objective function with nonnegativity constraints (since Poisson intensities are naturally nonnegative). We developed computational methods for solving the constrained sparse Poisson inverse problem and applied them to reconstruction problems arising in medical imaging. Applied and numerical linear algebra. Large-scale optimization problems require solving large systems of linear equations. Direct methods for solving such problems are impractical for time and memory reasons. Iterative methods offer realistic alternatives as they require only matrix-vector products. In interior-point method contexts, the large-scale linear systems are either unsymmetric or become ill-conditioned asymptotically. In this work, we developed approaches for curing the instabilities associated with solving such large systems of linear equations. In addition, we have developed stable numerical methods for solving linear systems arising in limited-memory quasi-Newton methods for large-scale optimization. A dedicated website for this grant is found at http://faculty.ucmerced.edu/rmarcia/NSF_SecondOrder.html, where computer codes and demos are publicly available for download. This research was widely disseminated at SIAM, IEEE, SPIE, ICIAM, ISMP, ICCOPT, and AMS/MAA meetings. In particular, PI Marcia has organized mini-symposia on imaging and optimization at SIAM conferences. This grant provided research training and opportunities for UC Merced undergraduate students (including women and underrepresented minorities).
