A Comparison of Compressed Sensing and Sparse Recovery Algorithms Applied to Simulation Data
Abstract
The move toward exascale computing for scientific simulations is placing new demands on compression techniques. It is expected that the I/O system will not be able to support the volume of data that is expected to be written out. To enable quantitative analysis and scientific discovery, we are interested in techniques that compress high-dimensional simulation data and can provide perfect or near-perfect reconstruction. In this paper, we explore the use of compressed sensing (CS) techniques to reduce the size of the data before they are written out. Using large-scale simulation data, we investigate how the sufficient sparsity condition and the contrast in the data affect the quality of reconstruction and the degree of compression. We provide suggestions for the practical implementation of CS techniques and compare them with other sparse recovery methods. Our results show that despite longer times for reconstruction, compressed sensing techniques can provide near perfect reconstruction over a range of data with varying sparsity.References
R. Berinde and P. Indyk. Sequential sparse matching pursuit. In Communication, Control, and Computing,
47th Annual Allerton Conference on, pages 36–43, Sept 2009.
R. Berinde, P. Indyk, and M. Ruzic. Practical near-optimal sparse recovery in the L1 norm. In Communication, Control, and Computing, 2008 46th Annual Allerton Conference on, pages 198–205, Sept 2008.
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via
the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1–122, January 2010.
E. Candes and J. Romberg. 1-magic: Recovery of sparse signals via convex programming.
http://users.ece.gatech.edu/˜justin/l1magic/, 2005.
E.J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. Information Theory, IEEE Transactions on, 52(2):489–509, Feb 2006.
E.J. Candes and T. Tao. Decoding by linear programming. Information Theory, IEEE Transactions on,
(12):4203–4215, Dec 2005.
E.J. Candes and T. Tao. Near-optimal signal recovery from random projections: Universal encoding
strategies? Information Theory, IEEE Transactions on, 52(12):5406–5425, Dec 2006.
H. Childs et al. In Situ Processing. In E. Wes Bethel, Hank Childs, and Charles Hansen, editors, High
Performance Visualization—Enabling Extreme-Scale Scientific Insight, pages 171–198. CRC Press/Francis–
Taylor Group, Boca Raton, FL, USA, 2012.
G. Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its
applications. Journal of Algorithms, 55(1):58 – 75, 2005.
W. Deng, W. Yin, and Y. Zhang. Group sparse optimization by alternating direction method. volume 8858, pages 88580R–88580R–15, September 2013.
D.L. Donoho. Compressed sensing. Information Theory, IEEE Transactions on, 52(4):1289–1306, April
Y. J. Fan and C. Kamath. Practical considerations in applying compressed sensing to simulation data. In
Proceedings of the IEEE Data Compression Conference, page 479, Piscataway, NJ, USA, 2015.
M.A.T. Figueiredo, R.D. Nowak, and S.J. Wright. Gradient projection for sparse reconstruction: Application
to compressed sensing and other inverse problems. Selected Topics in Signal Processing, IEEE Journal of,
(4):586–597, Dec 2007.
N. Fout and K.-L. Ma. Transform coding for hardware-accelerated volume rendering. Visualization and Computer Graphics, IEEE Transactions on, 13(6):1600–1607, Nov 2007.
S. B. Gokturk, C. Tomasi, B. Girod, and C. Beaulieu. Medical image compression based on region of interest,
with application to colon CT images. In Proceedings of the 23rd Annual EMBS International Conference,
pages 2453–2456, Piscataway, NJ, USA, 2001. IEEE.
Hcompress image compression software Web page, 2015. http://www.stsci.edu/software/hcompress.html.
P. Indyk, N. Koudas, and S. Muthukrishnan. Identifying representative trends in massive time series data sets using sketches. In Proceedings, Conference on Very Large Data Bases, pages 363–372, 2000.
P. Indyk and M. Ruzic. Near-optimal sparse recovery in the L1 norm. In Proceedings, 49th Symposium on
Foundations of Computer Science, pages 199–207, October 2008.
M. Isenburg, P. Lindstrom, and J. Snoeyink. Lossless compression of predicted floating-point geometry.
Comput. Aided Des., 37(8):869–877, July 2005.
J. Iverson, C. Kamath, and G. Karypis. Fast and effective lossy compression algorithms for scientific datasets. In Proceedings of the 18th International Conference on Parallel Processing, Euro-Par’12, pages 843–856,
Berlin, Heidelberg, 2012.
C. Kamath, J. Iverson, R. Kirk, and G. Karypis. Detection of coherent structures in extreme-scale simulations. In Proceedings of the Exascale Research Conference, April 2012.
D. Laney, S. Langer, C. Weber, P. Lindstrom, and A. Wegener. Assessing the effects of data compression
in simulations using physically motivated metrics. In Proceedings of the International Conference on High
Performance Computing, Networking, Storage and Analysis, SC ’13, pages 76:1–76:12, New York, NY, USA,
ACM.
Z. Lin, T. S. Hahm, W. W. Lee, W. M. Tang, and R. B. White. Turbulent transport reduction by zonal flows:
Massively parallel simulations. Science, (1835):281, 1998.
P. Lindstrom. Fixed-rate compressed floating-point arrays. Visualization and Computer Graphics, IEEE
Transactions on, 20(12):2674–2683, Dec 2014.
P. Lindstrom and M. Isenburg. Fast and efficient compression of floating-point data. Visualization and
Computer Graphics, IEEE Transactions on, 12(5):1245–1250, Sep-Oct 2006.
R. Saab, R. Wang, and O. Yilmaz. Near-optimal compression for compressed sensing. In Data Compression Conference (DCC), 2015, pages 113–122, April 2015.
M. Salloum, N. Fabian, D. M. Hensinger, and J. A. Templeton. Compressed sensing and reconstruction of
unstructured mesh datasets. arXiv:1508.06314, August 2015.
K. Sayood. Introduction to Data Compression (3rd Ed.). Morgan Kaufmann Publishers Inc., San Francisco,
CA, USA, 2005.
R. Soundararajan and S. Vishwanath. Quantization using compressive sensing. In Information Theory and
Applications Workshop (ITA), 2011, pages 1–6, Feb 2011.
J.A. Tropp and A.C. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit.
Information Theory, IEEE Transactions on, 53(12):4655–4666, Dec 2007.
J. Yang and Y. Zhang. Alternating direction algorithms for l1-problems in compressive sensing. SIAM Journal on Scientific Computing, 33(1):250–278, 2011.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
