A Comparison of Compressed Sensing and Sparse Recovery Algorithms Applied to Simulation Data

Ya Ju Fan, Chandrika Kamath

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.

Keywords


Compressed sensing; exascale computing; sparse recovery

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.


Full Text: PDF

DOI: 10.19139/soic.v4i3.207

Refbacks

  • There are currently no refbacks.