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.
made fundamental contributions to the fields of both numerical optimization and numerical linear algebra. In particular, this work developed new trust-region methods for solving large-scale unconstrained optimization problems, new primal and primal-dual interior-point methods for solving the compressed sensing problem in image processing, and backward-stable pivoting strategies for use in methods that factorize unsymmetric tridiagonal matrices. Grant-funded research opened new avenues for preconditioning by developing recursion formulas for solving various types of shifted quasi-Newton systems. These recursion formulas are especially useful in preconditioning block systems that arise in primal-dual penalty and interior-point methods. Results from this research was widely disseminated via journal publications, presentations at national and international conferences, and seminars at universities both in the US and abroad; code related to this grant work is publicly available on the PI’s website. An important component of this grant work was the training and education of graduate students in computational mathematics. The grant funded four students in the terminal Masters of Arts program in Mathematics at Wake Forest University. For all four students, it was their first exposure to research in computational mathematics. The PI guided students in extensive background reading, conducting literature searches, and implementing and testing proposed algorithms. Many of these students helped prepare manuscripts for submission. One student was particularly interested in applications of hyperspectral imaging and finished a Master’s thesis related to work on this grant. Two of these students have enrolled in PhD programs: one in computational math, another in computer science.
