# Case Study: Sparse Reconstruction Problems from SPARCO Toolbox

Instructions for optimization with PSG Run-File, PSG MATLAB Toolbox, PSG MATLAB Subroutines and PSG R.

PROBLEM: L1 Relaxed
Minimize Meanabs_pen (minimizing L1-error of regression)
subject to
Polynom_abs ≤ Const2 (constraint on the sum of absolute values of the components of decision vector)
Box constraints (bounds on variables)
——————————————————————–
Meanabs_pen = Mean Absolute Penalty
Polynom_abs = Polynomial Absolute
Box constraints = constraints on individual decision variables
——————————————————————–

Problem “problem_601_Relaxed”

Dataset1 4096 3200 6.48E+00 55.33 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data R R Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Sources of Data Takhar, D., Laska, J.N., Wakin, M., Duarte, M., Baron, D., Sarvotham, S., Kelly, K.K., Baraniuk, R.G.: A new camera architecture based on optical-domain compression. In: Proceedings of the IS&T/SPIE Symposium on Electronic Imaging: Computational Imaging, vol. 6065 (2006). Dataset2 ProblemStatement Data Solution 4096 3200 2.78E+00 1965.0 Dataset3 ProblemStatement Data Solution 4096 3200 8.42E-01 2894.0 Dataset4 ProblemStatement Data Solution 4096 3200 9.18E-08 509.2

Problem “problem_602_Relaxed”

Dataset1 4096 3200 6.80E+00 190.26 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data R R Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Sources of Data Takhar, D., Laska, J.N., Wakin, M., Duarte, M., Baron, D., Sarvotham, S., Kelly, K.K., Baraniuk, R.G.: A new camera architecture based on optical-domain compression. In: Proceedings of the IS&T/SPIE Symposium on Electronic Imaging: Computational Imaging, vol. 6065 (2006). Dataset2 ProblemStatement Data Solution 4096 3200 2.99E+00 2906.6 Dataset3 ProblemStatement Data Solution 4096 3200 3.60E-01 2982.0 Dataset4 ProblemStatement Data Solution 4096 3200 9.71E-05 272.6

PROBLEM: L1 Relaxed D
Minimize Meanabs_pen (minimizing L1-error of regression)
subject to
Linear ≤ Const1 (constraint on sum of components of decision vector)
Box constraints (bounds on variables)
——————————————————————–
Meanabs_pen = Mean Absolute Penalty
Box constraints = constraints on individual decision variables
——————————————————————–Problem “problem_2_Relaxed_Double”

Dataset1 1024 1024 1.22E+00 0.5 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Buckheit, J., Donoho, D.L.: Wavelets and Statistics, chap. Wavelab and reproducible research. Springer-Verlag, Berlin, New York (1995). URL http://citeseer.ist.psu.edu/article/buckheit95wavelab.html Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998). URL http://epubs.siam.org/SISC/volume-20/art30401.html Donoho, D.L., Johnstone, I.M.: Ideal spatial adaptation by wavelet shrinkage. Biometrika 81(3), 425-455 (1994). URL http://citeseer.ist.psu.edu/donoho93ideal.html Dataset2 ProblemStatement Data Solution 1024 1024 6.63E-01 0.6 Dataset3 ProblemStatement Data Solution 1024 1024 4.42E-02 4.5 Dataset4 ProblemStatement Data Solution 1024 1024 1.24E-014 2.8

Problem “problem_3_Relaxed_Double”

Dataset1 2048 1024 6.38E-01 0.5 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Berg, E.van den, Friedlander, M.P.: SPARCO: A toolbox for testing sparse reconstruction algorithms (2008). URL http://www.cs.ubc.ca/labs/scl/sparco/ Berg, E.van den, Friedlander, M.P., Hennenfent, G., Herrmann, F., Saab, R., Yilmaz, O.: Sparco: A testing framework for sparse reconstruction. Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver (2007) Dataset2 ProblemStatement Data Solution 2048 1024 0.0803 4.1 Dataset3 ProblemStatement Data Solution 2048 1024 0.00227 130.3 Dataset4 ProblemStatement Data Solution 2048 1024 4.58e-14 460.3

Problem “problem_5_Relaxed_Double”

Dataset1 2048 300 1.00E+00 0.5 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Berg, E.van den, Friedlander, M.P.: SPARCO: A toolbox for testing sparse reconstruction algorithms (2008). URL http://www.cs.ubc.ca/labs/scl/sparco/ Berg, E.van den, Friedlander, M.P., Hennenfent, G., Herrmann, F., Saab, R., Yilmaz, O.: Sparco: A testing framework for sparse reconstruction. Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver (2007) Dataset2 ProblemStatement Data Solution 2048 300 0.271 8 Dataset3 ProblemStatement Data Solution 2048 300 0.0579 1.8 Dataset4 ProblemStatement Data Solution 2048 300 2.43e-14 1.8

Problem “problem_6_Relaxed_Double”

Dataset1 2048 600 1.41E+02 1.4 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Candes, E.J., Romberg, J.: Practical signal recovery from random projections. In: Wavelet Applications in Signal and Image Processing XI, Proc. SPIE Conf. 5914. (2004) Dataset2 ProblemStatement Data Solution 2048 600 66.2 56.5 Dataset3 ProblemStatement Data Solution 2048 600 1.59 185.9 Dataset4 ProblemStatement Data Solution 2048 600 3.77e-12 30.9

Problem “problem_7_Relaxed_Double”

Dataset1 2560 600 5.81E-02 2.3 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Candes, E., Romberg, J.: L1-magic. http://www.l1-magic.org/ (2007) Dataset2 ProblemStatement Data Solution 2560 600 0.0339 7.9 Dataset3 ProblemStatement Data Solution 2560 600 0.0102 12.8 Dataset4 ProblemStatemen Data Solution 2560 600 1.37e-13 1.6

Problem “problem_8_Relaxed_Double”

Dataset1 2560 600 4.94E-02 6.0 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Candes, E., Romberg, J.: L1-magic. http://www.l1-magic.org/ (2007) Dataset2 ProblemStatement Data Solution 2560 600 0.0164 11.9 Dataset3 ProblemStatement Data Solution 2560 600 0.00329 11.6 Dataset4 ProblemStatement Data Solution 2560 600 1.36e-13 1.2

Problem “problem_9_Relaxed_Double”

Dataset1 128 128 3.14E-01 0.01 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998). URL http://epubs.siam.org/SISC/volume-20/art30401.html Donoho, D.L., Johnstone, I.M.: Ideal spatial adaptation by wavelet shrinkage. Biometrika 81(3), 425-455 (1994). URL http://citeseer.ist.psu.edu/donoho93ideal.html Dataset2 ProblemStatement Data Solution 128 128 0.093 0.02 Dataset3 ProblemStatement Data Solution 128 128 0.00781 0.02 Dataset4 ProblemStatement Data Solution 128 128 2.92e-13 0.04

Problem “problem_10_Relaxed_Double”

Dataset1 1024 1024 1.32E-01 0.5 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998). URL http://epubs.siam.org/SISC/volume-20/art30401.html Donoho, D.L., Johnstone, I.M.: Ideal spatial adaptation by wavelet shrinkage. Biometrika 81(3), 425-455 (1994). URL http://citeseer.ist.psu.edu/donoho93ideal.html Dataset2 ProblemStatement Data Solution 1024 1024 6.10E-02 0.6 Dataset3 ProblemStatement Data Solution 1024 1024 1.15E-02 0.7 Dataset4 ProblemStatement Data Solution 1024 1024 1.64E-12 143.1

Problem “problem_11_Relaxed_Double”

Dataset1 1024 256 1.22E+00 3.1 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Berg, E.van den, Friedlander, M.P.: SPARCO: A toolbox for testing sparse reconstruction algorithms (2008). URL http://www.cs.ubc.ca/labs/scl/sparco/ E.van den, Friedlander, M.P., Hennenfent, G., Herrmann, F., Saab, R., Yilmaz, O.: Sparco: A testing framework for sparse reconstruction. Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver (2007) Dataset2 ProblemStatement Data Solution 1024 256 0.518 6.5 Dataset3 ProblemStatement Data Solution 1024 256 0.129 35.5 Dataset4 ProblemStatement Data Solution 1024 256 2.53e-14 31.6

Problem “problem_603_Relaxed_Double”

Dataset1 4096 1024 3.35E-01 2.2 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. Selected Topics in Signal Processing, IEEE Journal of 1(4), 586-597 (2007). DOI 10.1109/JSTSP.2007.910281. URL http://www.lx.it.pt/~mtf/GPSR Dataset2 ProblemStatement Data Solution 4096 1024 0.175 10.7 Dataset3 ProblemStatement Data Solution 4096 1024 0.0416 1150.4 Dataset4 ProblemStatement Data Solution 4096 1024 2.32e-14 391

Problem “problem_902_Relaxed_Double”

Dataset1 1000 200 2.32E-02 0.07 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Hennenfent, G., Herrmann, F.J.: Sparseness-constrained data continuation with frames: Applications to missing traces and aliased signals in 2/3-D. In: SEG International Exposition and 75th Annual Meeting (2005). URL http://slim.eos.ubc.ca/Publications/Public/Conferences/SEG/hennenfent05seg.pdf Hennenfent, G., Herrmann, F.J.: Simply denoise: waveeld reconstruction via coarse nonuniform sampling. Tech. rep., UBC Earth & Ocean Sciences (2007) Herrmann, F.J., Hennenfent, G.: Non-parametric seismic data recovery with curvelet frames. Tech. rep., UBC Earth & Ocean Sciences Department (2007). TR-2007-1 URL http://slim.eos.ubc.ca/Publications/Public/Journals/CRSI.pdf Dataset2 ProblemStatement Data Solution 1000 200 0.0186 0.12 Dataset3 ProblemStatement Data Solution 1000 200 0.0036 0.12 Dataset4 ProblemStatement Data Solution 1000 200 3.12e-14 26.3

Problem “problem_903_Relaxed_Double”

Dataset1 1024 1024 6.17E-01 0.6 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Dossal, C., Mallat, S.: Sparse spike deconvolution with minimum scale. In: Proceedings of Signal Processing with Adaptive Sparse Structured Representations, pp. 123-126. Rennes, France (2005). URL http://spars05.irisa.fr/ACTES/PS2-11.pdf Dataset2 ProblemStatement Data Solution 1024 1024 0.406 1.4 Dataset3 ProblemStatement Data Solution 1024 1024 0.0992 29.7 Dataset4 ProblemStatement Data Solution 1024 1024 9.18e-05 10.7

PROBLEM: L2 D
Minimize Meansquare + Linear (minimizing L2-error of regression)
subject to
Linear ≤ Const3 (constraint on sum of components of decision vector)
Box constraints (bounds on variables)
——————————————————————–
Meansquare = Mean Square Penalty
Meanabs_pen = Mean Absolute Penalty
Box constraints = constraints on individual decision variables
——————————————————————–Problem “problem_2_L2_dbl”

Dataset1 1024 1024 2.98E+03 0.32 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Buckheit, J., Donoho, D.L.: Wavelets and Statistics, chap. Wavelab and reproducible research. Springer-Verlag, Berlin, New York (1995). URL http://citeseer.ist.psu.edu/article/buckheit95wavelab.html Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998). URL http://epubs.siam.org/SISC/volume-20/art30401.html Donoho, D.L., Johnstone, I.M.: Ideal spatial adaptation by wavelet shrinkage. Biometrika 81(3), 425-455 (1994). URL http://citeseer.ist.psu.edu/donoho93ideal.html Dataset2 ProblemStatement Data Solution 1024 1024 2310 0.32 Dataset3 ProblemStatement Data Solution 1024 1024 415 0.32 Dataset4 ProblemStatement Data Solution 1024 1024 44.7 0.32 Dataset5 ProblemStatement Data Solution 1024 1024 4.5 0.31

Problem “problem_3_L2_dbl”

Dataset1 2048 1024 2.37E+03 1.4 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Berg, E.van den, Friedlander, M.P.: SPARCO: A toolbox for testing sparse reconstruction algorithms (2008). URL http://www.cs.ubc.ca/labs/scl/sparco/ Berg, E.van den, Friedlander, M.P., Hennenfent, G., Herrmann, F., Saab, R., Yilmaz, O.: Sparco: A testing framework for sparse reconstruction. Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver (2007) Dataset2 ProblemStatement Data Solution 2048 1024 1310 1.4 Dataset3 ProblemStatement Data Solution 2048 1024 178 2.7 Dataset4 ProblemStatement Data Solution 2048 1024 21.6 10.8 Dataset5 ProblemStatement Data Solution 2048 1024 2.22 102.8

Problem “problem_5_L2_dbl”

Dataset1 2048 300 2.10E+03 1.6 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Berg, E.van den, Friedlander, M.P.: SPARCO: A toolbox for testing sparse reconstruction algorithms (2008). URL http://www.cs.ubc.ca/labs/scl/sparco/ Berg, E.van den, Friedlander, M.P., Hennenfent, G., Herrmann, F., Saab, R., Yilmaz, O.: Sparco: A testing framework for sparse reconstruction. Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver (2007) Dataset2 ProblemStatement Data Solution 2048 300 1230 1.9 Dataset3 ProblemStatement Data Solution 2048 300 158 8.8 Dataset4 ProblemStatement Data Solution 2048 300 17.8 85.7 Dataset5 ProblemStatement Data Solution 2048 300 1.82 837.4

Problem “problem_6_L2_dbl”

Dataset1 2048 600 1.29E+07 1.8 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Candes, E.J., Romberg, J.: Practical signal recovery from random projections. In: Wavelet Applications in Signal and Image Processing XI, Proc. SPIE Conf. 5914. (2004) Dataset2 ProblemStatement Data Solution 2048 600 5.29e+06 2.4 Dataset3 ProblemStatement Data Solution 2048 600 1.46e+06 9.5 Dataset4 ProblemStatement Data Solution 2048 600 170000 87.4 Dataset5 ProblemStatement Data Solution 2048 600 17600 636.5 Dataset6 ProblemStatement Data Solution 2048 600 4200 112.4 Dataset7 ProblemStatement Data Solution 2048 600 460 6.4

Problem “problem_7_L2_dbl”

Dataset1 2560 600 2.25E+00 2.03 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Candes, E., Romberg, J.: L1-magic. http://www.l1-magic.org/ (2007) Dataset2 ProblemStatement Data Solution 2560 600 1.56 3 Dataset3 ProblemStatement Data Solution 2560 600 0.89 2.52 Dataset4 ProblemStatement Data Solution 2560 600 0.196 2.88

Problem “problem_8_L2_dbl”

Dataset1 2560 600 2.11E+00 2.76 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Candes, E., Romberg, J.: L1-magic. http://www.l1-magic.org/ (2007) Dataset2 ProblemStatement Data Solution 2560 600 1.52 3 Dataset3 ProblemStatement Data Solution 2560 600 0.881 3.24 Dataset4 ProblemStatement Data Solution 2560 600 0.195 5.91

Problem “problem_9_L2_dbl”

Dataset1 128 128 1.68E+02 0.48 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998). URL http://epubs.siam.org/SISC/volume-20/art30401.html Donoho, D.L., Johnstone, I.M.: Ideal spatial adaptation by wavelet shrinkage. Biometrika 81(3), 425-455 (1994). URL http://citeseer.ist.psu.edu/donoho93ideal.html Dataset2 ProblemStatement Data Solution 128 128 116 0.98 Dataset3 ProblemStatement Data Solution 128 128 36.5 1.47 Dataset4 ProblemStatement Data Solution 128 128 5.54 2.41 Dataset5 ProblemStatement Data Solution 128 128 3.98 2.4

Problem “problem_10_L2_dbl”

Dataset1 1024 1024 2.04E+03 150.9 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998). URL http://epubs.siam.org/SISC/volume-20/art30401.html Donoho, D.L., Johnstone, I.M.: Ideal spatial adaptation by wavelet shrinkage. Biometrika 81(3), 425-455 (1994). URL http://citeseer.ist.psu.edu/donoho93ideal.html Dataset2 ProblemStatement Data Solution 1024 1024 666 281.3 Dataset3 ProblemStatement Data Solution 1024 1024 415 441.9 Dataset4 ProblemStatement Data Solution 1024 1024 101 651.7 Dataset5 ProblemStatement Data Solution 1024 1024 20.7 1848.6

Problem “problem_11_L2_dbl”

Dataset1 1024 256 1.80E+03 0.5 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Berg,E.van den, Friedlander, M.P.: SPARCO: A toolbox for testing sparse reconstruction algorithms (2008). URL http://www.cs.ubc.ca/labs/scl/sparco/ Berg, E.van den, Friedlander, M.P., Hennenfent, G., Herrmann, F., Saab, R., Yilmaz, O.: Sparco: A testing framework for sparse reconstruction. Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver (2007) Dataset2 ProblemStatement Data Solution 1024 256 233 1.9 Dataset3 ProblemStatement Data Solution 1024 256 24 20 Dataset4 ProblemStatement Data Solution 1024 256 2.4 179.4 Dataset5 ProblemStatement Data Solution 1024 256 0.719 1.1

Problem “problem_601_L2_dbl”

Dataset1 4096 3200 8.78E+05 204.8 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Takhar, D., Laska, J.N., Wakin, M., Duarte, M., Baron, D., Sarvotham, S., Kelly, K.K., Baraniuk, R.G.: A new camera architecture based on optical-domain compression. In: Proceedings of the IS&T/SPIE Symposium on Electronic Imaging: Computational Imaging, vol. 6065 (2006). Dataset2 ProblemStatement Data Solution 4096 3200 246000 800.8 Dataset3 ProblemStatement Data Solution 4096 3200 191000 1215.5 Dataset4 ProblemStatement Data Solution 4096 3200 561000 2179.5 Dataset5 ProblemStatement Data Solution 4096 3200 1.05e+06 473.6

Problem “problem_602_L2_dbl”

Dataset1 4096 3200 3.62E+05 687.5 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Takhar, D., Laska, J.N., Wakin, M., Duarte, M., Baron, D., Sarvotham, S., Kelly, K.K., Baraniuk, R.G.: A new camera architecture based on optical-domain compression. In: Proceedings of the IS&T/SPIE Symposium on Electronic Imaging: Computational Imaging, vol. 6065 (2006). Dataset2 ProblemStatement Data Solution 4096 3200 266000 679.8 Dataset3 ProblemStatement Data Solution 4096 3200 294000 255.5

Problem “problem_603_L2_dbl”

Dataset1 4096 1024 1.21E+02 6.6 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. Selected Topics in Signal Processing, IEEE Journal of 1(4), 586-597 (2007). DOI 10.1109/JSTSP.2007.910281. URL http://www.lx.it.pt/~mtf/GPSR Dataset2 ProblemStatement Data Solution 4096 1024 21.4 18.6 Dataset3 ProblemStatement Data Solution 4096 1024 2.54 168.3

Problem “problem_902_L2_dbl”

Dataset1 1000 200 1.01E-01 0.3 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Hennenfent, G., Herrmann, F.J.: Sparseness-constrained data continuation with frames: Applications to missing traces and aliased signals in 2/3-D. In: SEG International Exposition and 75th Annual Meeting (2005). URL http://slim.eos.ubc.ca/Publications/Public/Conferences/SEG/hennenfent05seg.pdf Hennenfent, G., Herrmann, F.J.: Simply denoise: waveeld reconstruction via coarse nonuniform sampling. Tech. rep., UBC Earth & Ocean Sciences (2007) Herrmann, F.J., Hennenfent, G.: Non-parametric seismic data recovery with curvelet frames. Tech. rep., UBC Earth & Ocean Sciences Department (2007). TR-2007-1 URL http://slim.eos.ubc.ca/Publications/Public/Journals/CRSI.pdf Dataset2 ProblemStatement Data Solution 1000 200 0.0167 0.5 Dataset3 ProblemStatement Data Solution 1000 200 0.00173 2

Problem “problem_903_L2_dbl”

Dataset1 1024 1024 8.70E+02 68.1 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) Environments Run-File Problem Statement Data Solution Matlab Toolbox Data Matlab Subroutines Matlab Code Data

Instructions for importing problems from Run-File to PSG MATLAB.

 Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Dossal, C., Mallat, S.: Sparse spike deconvolution with minimum scale. In: Proceedings of Signal Processing with Adaptive Sparse Structured Representations, pp. 123-126. Rennes, France (2005). URL http://spars05.irisa.fr/ACTES/PS2-11.pdf Dataset2 ProblemStatement Data Solution 1024 1024 118 167.2 Dataset3 ProblemStatement Data Solution 1024 1024 12.9 170.9 Dataset4 ProblemStatement Data Solution 1024 1024 1.41 263 Dataset5 ProblemStatement Data Solution 1024 1024 0.458 530.4

CASE STUDY SUMMARY
SPARCO is a suite of problems for testing and benchmarking algorithms for sparse signal reconstruction, Berg et al. (2007, 2008). It is also an environment for creating new test problems. Also a suite of standard linear operators is provided from which new problems can be assembled. SPARCO is implemented entirely in MATLABand is self contained.
This case study presents problem formulations and its solutions for a set of sparse reconstruction problems taken from SPARCO toolbox.
Problems included in the SPARCO toolbox were initially considered by different authors in different application areas: imaging, compressed sensing, geophysics, information compressing, etc. Relevant references can be found in the SPARCO toolbox.
The objective of Sparse Reconstruction is to find a decision vector which has a small number of non-zero components and satisfies exactly or almost exactly a system of linear equations. There are many variants of optimization formulations of such problems.
This case study is described in paper Boyko et al. (2011).
We solved many problems included in SPARCO toolbox problems in so called “L1Relaxed D” formulation. “L1Relaxed D” minimizes L1-error of regression with one linear inequality on the sum of decision vector components; the decision vector components are nonnegative (number of decision variables is doubled to achieve non-negativity). The non-negativity of variables is quite important because an optimal vector contains many zero variables. To investigate property of solution we solved various problems with different values of upper bound in the linear inequality and calculated cardinality and max functions in optimal points.
Some problems were solved in so called “L1Relaxed” formulation with original set of variables (without doubling the number of variables to achieve non-negativity). Variables are bounded by box constraints in this formulation. For these problems “L1Relaxed” formulation is more effective compared to “L1Relaxed D” formulation.
Additionally many problems were solved in so called “L2 D” or LASSO formulation which also has double set of variables but does not have constraints.
Sum of decision variables multiplied by some coefficient is used as regularization term in the objective function.
This problem can be easy solved by methods for unconstrained optimization.
We used SPARCO toolbox software to extract data for the considered problems. SPARCO toolbox provides a set of operators to deal with data.
We converted the problems data to PSG format and solved them in PSG Run-File envoronment.
In the problem formulations we have included several “dummy” functions multiplied by 0 (zero). Such “dummy” functions do not not impact solution process, but values of these functions are printed in the final solution file.

For instance, you can view many “dummy” functions in the following problem formulation:
problem: problem_602_Relaxed_700, type = minimize
objective: objective_new, linearize = 1
meanabs_pen_obj(matrix_ab602)
constraint: constraint_card, upper_bound = 700, linearize = 1
polynom_abs_S(matrix_card4096)
0 * cardn_1(1.,matrix_card4096)
0 * cardn_2(0.1,matrix_card4096)
0 * cardn_3(0.01,matrix_card4096)
0 * cardn_4(0.001,matrix_card4096)
0 * cardn_5(0.0001,matrix_card4096)
0 * cardn_6(0.00001,matrix_card4096)
0 * max_comp_pos_7(matrix_card4096)
0 * max_comp_neg_8(matrix_card4096)
box_of_variables: lowerbounds = -40, upperbounds = +40
Solver: van, precision = 4, stages = 6, timelimit = 3600
The corresponding solution file includes values of “dummy” functions on the final optimal point:
Problem: solution_status = optimal
Variables: optimal_point = point_problem_602_Relaxed_700
Objective: objective_new = 9.71029929057e-005
Constraint: constraint_card = 6.968284830013e+002 [-3.171516998665e+000]
Function: meanabs_pen_obj(matrix_ab602) = 9.710299290575e-005
Function: polynom_abs_s(matrix_card4096) = 6.968284830013e+002
Function: cardn_1(0.100000E+01,matrix_card4096) = 1.420000000000e+002
Function: cardn_2(0.100000E+00,matrix_card4096) = 7.890000000000e+002
Function: cardn_3(0.100000E-01,matrix_card4096) = 3.043000000000e+003
Function: cardn_4(0.100000E-02,matrix_card4096) = 3.964000000000e+003
Function: cardn_5(0.100000E-03,matrix_card4096) = 4.079000000000e+003
Function: cardn_6(0.100000E-04,matrix_card4096) = 4.095000000000e+003
Function: max_comp_pos_7(matrix_card4096) = 1.616083034336e+001
Function: max_comp_neg_8(matrix_card4096) = 6.562008879305e+000
References
• Berg, E.V., Friedlander, M.P., Hennenfent, G., Herrmann, F., Saab, R., and O., Yilmaz (2007): SPARCO: A testing framework for sparse reconstruction. Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver.
• Berg, E.V., and M.P., Friedlander (2008): SPARCO: A toolbox for testing sparse reconstruction algorithms. URL http://www.cs.ubc.ca/labs/scl/sparco/
• Boyko, N., Karamemis, G., Kuzmenko, V. and S. Uryasev (2011): Sparse Signal Reconstruction: a Cardinality Approach. Submitted for publication (download http://www.ise.ufl.edu/uryasev/Sparse_Signal_Reconstruction_Cardinality_Approach.pdf).