Collaborative Research:
Second-Order Methods for Large-Scale Optimization in Compressed Sensing

Principal Investigators:
Roummel Marcia, University of California, Merced
Jennifer Erway, Wake Forest University
Rebecca Willett, Duke University
Supported by NSF Grants DMS-09-65711 (formerly DMS-0811062) and DMS-08-11106


Summary of results. This research aims at the development of efficient methods for solving compressed sensing (CS) minimization problems. The research accomplishments supported by this NSF grant thus far include the following:

1. Shifted limited-memory quasi-Newton methods. We developed methods to solve shifted L-BFGS systems where the shifts can include any symmetric positive-definite matrix (e.g., positive-definite diagonal, tridiagonal, circulant matrices). Shifted limited-memory systems of equations are important in the context of trust-region methods. These types of systems also appear when preconditioning interior-point methods. The research began as the result of applying a preconditioner in a second-order method for solving the CS problem.

2. Second-order trust-region methods for unconstrained optimization. This research centered on trust-region methods for use in interior-point methods. We developed an iterative trust-region method for large-scale optimization that allows for the choice in norm to be independent of the preconditioner. Until this research, the choice of preconditioner was tied to the norm choice, meaning that if the Hessian changes dramatically between iterations, the shape of the trust-region also dramatically changes.

3. Compressive coded aperture imaging. We developed practical imaging systems that are physically realizable and mechanically robust using a pattern of openings that results in compressive observations. In addition, the corresponding projection matrix satisfies important statistical properties that are needed to guarantee high-accuracy recovery. The reconstructions from our proposed camera architecture preserve many of the details that would normally be lost from low-resolution observations.

4. Constrained compressed sensing optimization methods. In imaging problems, the signal of interest is naturally nonnegative since the pixel values correspond to light intensity, which cannot be less than zero. This a priori knowledge can be incorporated within the CS minimization problem as constraints but results in a more difficult optimization problem. We developed methods for solving such problems and applied them to imaging problems in astronomy.

5. Poisson compressed sensing. Under low-light conditions, photon counts are very limited. The noise in these settings is better modeled by Poisson statistics rather than by a Gaussian distribution, which is the usual assumption in the compressed sensing framework. Thus, an objective function different from the conventional CS minimization problem must be used. We not only demonstrated performance guarantees in Poisson CS settings but also developed gradient-based algorithms for solving Poisson CS minimization problems.

6. Applications in hyperspectral imaging. Hyperspectral imaging involves taking images at various spectral wavelengths. For nearby bandwidths, the spectral information can be redundant, and thus, dimension-reduction techniques can more compactly express the data by eliminating redundancy before storing and transmitting data. In [28], we applied a randomized SVD method to several large hyperspectral data sets and found it effective for lossless compression, target detection, and classification. In [24], we found that using prolate spheroidal wave functions as a basis for orthogonal projection results in better hyperspectral data reconstruction than compressive projection principal component analysis.

7. Stable solutions of unsymmetric tridiagonal linear systems. 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 alterna- tives as they require only matrix-vector products. We developed ways of factorizing unsymmetric tridiagonal matrices to overcome some of the instabilities associated with the Lanczos method when applied to unsymmetric matrices. The factorization we proposed is backward stable and when used in conjunction with the Lanczos method and applied to symmetric positive-definite matrices, reduces to the well-known conjugate gradient method.


Publications. This research grant has thus far resulted in the following articles:
  1. Jennifer Erway and Philip Gill, A subspace minimization method for the trust-region step, SIAM Journal on Optimization, 20(3):1439-1461, 2009.
  2. Jennifer Erway, Vibhor Jain, and Roummel Marcia, Shifted L-BFGS systems, Technical Report 2012-6, Wake Forest University, 2012.
  3. Jennifer Erway and Roummel Marcia, A backward stability analysis of diagonal pivoting methods for solving unsymmetric tridiagonal systems without interchanges, Numerical Linear Algebra with Applications, 18(1):41-54, 2011.
  4. Jennifer Erway and Roummel Marcia, Limited-memory BFGS systems with diagonal updates, Linear Algebra and its Applications, 437:1, pp. 333-344, 2012.
  5. Jennifer Erway and Roummel Marcia, Solving limited-memory BFGS systems with generalized diagonal updates, in Proceedings of 2012 International Conference of Applied and Engineering Mathematics, London, UK, 2012.
  6. Jennifer Erway and Roummel Marcia, MSS: MATLAB software for L-BFGS trust-region subproblems for large-scale optimization, Technical Report 2012-5, Wake Forest University, 2012.
  7. Jennifer Erway, Roummel Marcia, and Joseph Tyson, Generalized diagonal pivoting methods for tridiagonal systems without interchanges, IAENG International Journal of Applied Mathematics, 4:40, pp. 269-275, 2010.
  8. Jennifer Erway, Roummel Marcia, and Joseph Tyson, On solving unsymmetric tridiagonal systems without interchanges, in Proceedings of the 2010 International Conference on Applied and Engineering Mathematics, London, UK, June 2010. (Best paper award)
  9. Zachary Harmany, Roummel Marcia, and Rebecca Willett, Sparse Poisson intensity reconstruction algorithms, in Proceedings of IEEE Statistical Signal Processing Workshop, Cardiff, Wales, UK, Sept. 2009.
  10. Zachary Harmany, Roummel Marcia, and Rebecca Willett, Sparsity-regularized photon-limited imaging, in Proceedings of IEEE International Symposium on Biomedical Imaging, Rotterdam, The Netherlands, April 2010.
  11. Zachary Harmany, Roummel Marcia, and Rebecca Willett, SPIRAL out of convexity: Sparsity-regularized algorithms for photon-limited imaging, in Proceedings of the 2010 IS&T/SPIE Electronic Imaging: Computational Imaging VIII, volume 7533, San Jose, CA, USA, 2010.
  12. Zachary Harmany, Roummel Marcia, and Rebecca Willett, This is SPIRAL-TAP: Sparse Poisson intensity reconstruction algorithms - theory and practice, IEEE Trans. Image Processing, 21:3, pp. 1084-1096, 2012.
  13. Zachary Harmany, Albert Oh, Roummel Marcia, and Rebecca Willett, Motion-adaptive compressive coded apertures, in Proceedings of the 2011 SPIE Optics and Photonics, San Diego, CA, USA, September 2011.
  14. Zachary Harmany, Daniel Thompson, Rebecca Willett, and Roummel Marcia, Gradient projection for linearly constrained convex optimization in sparse signal recovery, in Proceedings of the IEEE International Conference on Image Processing, Hong Kong, September 2010.
  15. James Hernandez, Zachary Harmany, Daniel Thompson, and Roummel Marcia, Bounded gradient projection methods for sparse signal recovery, in Proceedings of 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, Prague, Czech Republic, May 2011.
  16. David Jones, Rachel Schlick, and Roummel Marcia, Compressive video recovery with upper and lower bound constraints, in Proceedings of 2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, Kyoto, Japan, May 2012.
  17. Roummel Marcia, Zachary Harmany, and Rebecca Willett, Compressive coded aperture imaging, in Proceedings of the 2009 IS&T/SPIE Electronic Imaging: Computational Imaging VII, volume 7246, San Jose, CA, USA, Jan. 2009.
  18. Roummel Marcia, Zachary Harmany, and Rebecca Willett, Compressive coded apertures for high-resolution imaging, in Proceedings of the 2010 IS&T/SPIE Photonics Europe, volume 7723, Brussels, Belgium, April 2010.
  19. Roummel Marcia, Zachary Harmany, and Rebecca Willett, Compressive optical imaging: Architectures and algorithms, in G. Cristobal, P. Schelkens, and H. Thienpont, editors, Optical and Digital Image Processing. Wiley, 2010.
  20. Maxim Raginsky, Sina Jafarpour, Zachary Harmany, Roummel Marcia, Rebecca Willett, and Robert Calderbank, Performance bounds for expander-based compressed sensing in Poisson noise, IEEE Trans. Signal Process., 59:9, pp. 4139-4153, 2011.
  21. Maxim Raginsky, Roummel Marcia, Jorge Silva, and Rebecca Willett, Sequential probability assignment via online convex programming using exponential families, in IEEE International Symposium on Information Theory, Seoul, South Korea, June 2009.
  22. Maxim Raginsky, Rebecca Willett, Corin Horn, Jorge Silva, and Roummel Marcia, Sequential anomaly detection in the presence of noise and limited feedback, IEEE Trans. Information Theory, 8:58, pp. 5544-5562, 2012.
  23. Maxim Raginsky, Rebecca Willett, Zachary Harmany, and Roummel Marcia, Compressed sensing performance bounds under Poisson noise, IEEE Trans. Signal Process., 58:8, pp. 3990-4002, 2010.
  24. Seda Senay and Roummel Marcia, Dimensionality reduction and reconstruction for hyperspectral images using discrete prolate spheroidal sequences , in Signal and Image Processing, IASTED Conference, Honolulu, HI, 2012.
  25. Daniel Thompson, Zachary Harmany, and Roummel Marcia, Sparse video recovery using linearly constrained gradient projection, in Proceedings of 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, Prague, Czech Republic, May 2011.
  26. Rebecca Willett, Zachary Harmany, and Roummel Marcia, Poisson image reconstruction with total variation regularization, in Proceedings of the IEEE International Conference on Image Processing, Hong Kong, September 2010.
  27. Rebecca Willett, Roummel Marcia, and Jonathan Nichols, Compressive sensing for practical optical imaging systems: A tutorial, Optical Engineering, 50:7, pp. 1-13, 2011.
  28. Jiani Zhang, Jennifer Erway, Xiaofei Hu, Qiang Zhang, and Robert Plemmons, Randomized SVD methods in hyperspectral imaging, Journal of Electrical and Computer Engineering, Vol 2012, Article ID 409357:15 pages, 2012.

Software. Methods developed and implemented for this grant include the following (links to source codes are underlined):
Students. This grant has provided research training and opportunity for the following students:

UC Merced: Wake Forest: Duke University:
Presentations. The results of this grant have been presented at the following conferences, workshops, and seminars:

INFORMS Annual Meeting, Phoenix, AZ, October, 2012
IEEE Photonics Conference 2012, San Francisco, CA, September, 2012
International Symposium on Mathematical Programming, Berlin, Germany, August, 2012
Mathematical Association of America MathFest 2012, Madison, WI, August, 2012
SIAM Annual Meeting, Minneapolis, MN, July, 2012
2012 International Conference of Applied and Engineering Mathematics, London, UK, July, 2012
ALAMA Meeting 2012, Madrid, Spain, June, 2012
SIAM Conference on Applied Linear Algebra, Valencia, Spain, June, 2012
3rd Conference on Optimization Methods and Software, Chania, Crete, Greece, May, 2012
IEEE International Conference on Acoustic, Speech, and Signal Processing, Kyoto, Japan, March, 2012
INFORMS Optimization Society Conference, Miami, FL, February, 2012
UC LEADS Symposium, San Diego, CA, February, 2012
Joint Mathematics Meeting, Boston, MA, January, 2012
INFORMS Annual Meeting, Charlotte, NC, November, 2011
Mathematical Association of America MathFest 2011, Lexington, KY, August, 2011
International Congress on Industrial and Applied Mathematics, Vancouver, BC, July, 2011
IEEE International Conference on Acoustic, Speech, and Signal Processing, Prague, Czech Republic, May, 2011
SIAM Conference on Optimization, Darmstadt, Germany, May, 2011
Joint Mathematics Meeting, New Orleans, LA, January 2011
IEEE International Conference on Image Processing, Hong Kong, China, September 2010
Mathematical Association of America MathFest 2010, Pittsburgh, PA, August 2010
International Conference on Continuous Optimization (ICCOPT), Santiago, Chile, July 2010
International Conference on Applied and Engineering Mathematics, London, UK, July 2010
IEEE International Symposium on Biomedical Imaging, Rotterdam, The Netherlands, April 2010
SPIE Photonics Europe, Brussels, Belgium, April 2010
SPIE Photonics, San Jose, CA, January 2010
Joint Mathematics Meeting, San Francisco, CA, January 2010
SAMPLe Seminar, University of California, Merced, November 2009
SIAM Applied Linear Algebra, Monterey, CA, October 2009 [Slides].
IEEE Workshop on Statistical Signal Processing, Cardiff, United Kingdom, September 2009
International Symposium on Mathematical Programming, Chicago, IL, August, 2009
Northern Illinois University - Linear Algebra and Numerical Linear Algebra, DeKalb, IL, August 2009
IMACS World Congress, Athens, GA, August 2009
SIAM Annual Meeting, Denver, CO, July 2009
IEEE International Symposium on Information Theory, Seoul, South Korea, June 2009



Any opinions, findings and conclusions or recommendations expressed in the publications supported by this grant are those of the author(s) and do not necessarily reflect the views of the NSF.