# Case Study: Sparse Reconstruction Problems from SPARCO toolbox in PSG MATLAB Environment (fnext)

Instructions for optimization with PSG Run-File.

If you want to run this Case Study click on the following link to extract M-files and problem statement to the directory
…\PSG\MATLAB\CS_Sparse_Reconstruction_SPARCO: M-files for CS_Sparse_Reconstruction_Sparco_Matlab
PROBLEM: L2 form
Minimize 0.5*Quadratic + Const*Linear (minimizing L2-error of regression plus linear regularization term)
subject to
Box constraints (bounds on variables)
——————————————————————–
Box constraints = constraints on individual decision variables
——————————————————————–

Problem "problem_2_L2_dblExt"
 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 20 1024 1024 2.978E+03 0.001 Dataset2 Problem Statement Solution 10 1024 1024 2.312E+03 0.01 Dataset3 Problem Statement Solution 1 1024 1024 4.153E+02 0.01 Dataset4 Problem Statement Solution 0.1 1024 1024 4.471E+01 0.01 Dataset5 Problem Statement Solution 0.01 1024 1024 4.503E+00 0.19
Problem "problem_3_L2_dblExt"

 Problem Datasets Const # 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) Dataset1 Problem Statement Solution 20 2048 1024 2.369E+03 0.02 Dataset2 Problem Statement Solution 10 2048 1024 1.308E+03 0.02 Dataset3 Problem Statement Solution 1 2048 1024 1.780E+02 0.05 Dataset4 Problem Statement Solution 0.1 2048 1024 2.164E+01 0.18 Dataset5 Problem Statement Solution 0.01 2048 1024 2.217E+00 2.57
Problem "problem_5_L2_dblExt"

 Problem Datasets Const # 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) Dataset1 Problem Statement Solution 20 2048 300 2.104E+03 0.04 Dataset2 Problem Statement Solution 10 2048 300 1.226E+03 0.04 Dataset3 Problem Statement Solution 1 2048 300 1.580E+02 0.17 Dataset4 Problem Statement Solution 0.1 2048 300 1.778E+01 1.67 Dataset5 Problem Statement Solution 0.01 2048 300 1.810E+00 19.24
Problem "problem_6_L2_dblExt"

 Problem Datasets Const # 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) Dataset1 Problem Statement Solution 20000 2048 600 1.295E+07 0.5 Dataset2 Problem Statement Solution 10000 2048 600 9.652E+06 0.8 Dataset3 Problem Statement Solution 1000 2048 600 1.586E+06 3.6 Dataset4 Problem Statement Solution 100 2048 600 1.722E+05 36.8 Dataset5 Problem Statement Solution 10 2048 600 1.745E+04 385.6
Problem "problem_7_L2_dblExt"

 Problem Datasets Const # 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) Dataset1 Problem Statement Solution 0.2 2560 600 2.252E+00 0.07 Dataset2 Problem Statement Solution 0.1 2560 600 1.562E+00 0.10 Dataset3 Problem Statement Solution 0.05 2560 600 8.905E-01 0.11 Dataset4 Problem Statement Solution 0.02 2560 600 3.825E-01 0.15 Dataset5 Problem Statement Solution 0.01 2560 600 1.956E-01 0.19
Problem "problem_8_L2_dblExt"

 Problem Datasets Const # 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) Dataset1 Problem Statement Solution 0.2 2560 600 4.381E+00 0.09 Dataset2 Problem Statement Solution 0.1 2560 600 3.799E+00 0.11 Dataset3 Problem Statement Solution 0.05 2560 600 3.156E+00 0.13 Dataset4 Problem Statement Solution 0.01 2560 600 2.470E+00 0.23
Problem "problem_9_L2_dblExt"

 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 10 128 128 1.676E+02 0.8 Dataset2 Problem Statement Solution 5 128 128 1.161E+02 2.4 Dataset3 Problem Statement Solution 1 128 128 3.647E+01 3.9 Dataset4 Problem Statement Solution 0.05 128 128 5.563E+00 6.5 Dataset5 Problem Statement Solution 0.01 128 128 3.999E+00 6.5
Problem "problem_10_L2_dblExt"

 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 10 1024 1024 2.040E+03 3.3 Dataset2 Problem Statement Solution 1 1024 1024 6.638E+02 33.9 Dataset3 Problem Statement Solution 0.5 1024 1024 4.115E+02 29.7 Dataset4 Problem Statement Solution 0.1 1024 1024 9.543E+01 342.5 Dataset5 Problem Statement Solution 0.01 1024 1024 1.147E+01 1619.9
Problem "problem_11_L2_dblExt"

 Problem Datasets Const # 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) Dataset1 Problem Statement Solution 100 1024 256 1.801E+03 0.01 Dataset2 Problem Statement Solution 10 1024 256 2.333E+02 0.06 Dataset3 Problem Statement Solution 1 1024 256 2.396E+01 0.62 Dataset4 Problem Statement Solution 0.1 1024 256 2.403E+00 7.39
Problem "problem_401_L2_dblExt"

 Problem Datasets Const # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Database of Creative Commons licensed sounds (2007). URL http://freesound.iua.upf.edu Dataset1 Problem Statement Solution 2 57344 29166 2.431E+02 1.2 Dataset2 Problem Statement Solution 1 57344 29166 2.273E+02 3.1 Dataset3 Problem Statement Solution 0.5 57344 29166 1.849E+02 8.2 Dataset4 Problem Statement Solution 0.2 57344 29166 1.152E+02 23.5
Problem "problem_402_L2_dblExt"

 Problem Datasets Const # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec) Sources of Data Database of Creative Commons licensed sounds (2007). URL http://freesound.iua.upf.edu Dataset1 Problem Statement Solution 2 57344 29166 2.643E+02 1.8 Dataset2 Problem Statement Solution 1 57344 29166 2.473E+02 4.4 Dataset3 Problem Statement Solution 0.5 57344 29166 2.007E+02 13.9 Dataset4 Problem Statement Solution 0.2 57344 29166 1.248E+02 32.1
Problem "problem_403_L2_dblExt"

 Problem Datasets Const # 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) Dataset1 Problem Statement Solution 10 196608 196608 1.124E+04 2.7 Dataset2 Problem Statement Solution 3.3 196608 196608 6.174E+03 3.0 Dataset3 Problem Statement Solution 1 196608 196608 2.530E+03 3.1 Dataset4 Problem Statement Solution 0.33 196608 196608 1.136E+03 10.0 Dataset5 Problem Statement Solution 0.1 196608 196608 4.802E+02 35.2
Problem "problem_601_L2_dblExt"

 Problem Datasets Const # 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). Dataset1 Problem Statement Solution 10000 4096 3200 8.474E+05 420.7 Dataset2 Problem Statement Solution 1000 4096 3200 1.948E+05 598.0 Dataset3 Problem Statement Solution 500 4096 3200 1.187E+05 808.1 Dataset4 Problem Statement Solution 200 4096 3200 5.741E+04 1460.1 Dataset5 Problem Statement Solution 100 4096 3200 3.170E+04 1444.7
Problem "problem_602_L2_dblExt"

 Problem Datasets Const # 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). Dataset1 Problem Statement Solution 1000 4096 3200 3.165E+05 543.6 Dataset2 Problem Statement Solution 500 4096 3200 2.086E+05 848.9 Dataset3 Problem Statement Solution 200 4096 3200 1.049E+05 1117.9 Dataset4 Problem Statement Solution 100 4096 3200 5.745E+04 2038.8
Problem "problem_603_L2_dblExt"

 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 5 4096 1024 2.963E+02 0.21 Dataset2 Problem Statement Solution 2 4096 1024 1.893E+02 0.20 Dataset3 Problem Statement Solution 1 4096 1024 1.210E+02 0.20 Dataset4 Problem Statement Solution 0.1 4096 1024 2.145E+01 0.79 Dataset5 Problem Statement Solution 0.01 4096 1024 2.544E+00 6.64
Problem "problem_701_L2_dblExt"

 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 10 65536 65536 6.911E+03 0.59 Dataset2 Problem Statement Solution 5 65536 65536 4.336E+03 0.67 Dataset3 Problem Statement Solution 2 65536 65536 2.110E+03 0.75 Dataset4 Problem Statement Solution 1 65536 65536 1.198E+03 0.88
Problem "problem_702_L2_dblExt"

 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 0.05 16384 16384 2.484E+00 0.30 Dataset2 Problem Statement Solution 0.04 16384 16384 2.470E+00 0.55 Dataset3 Problem Statement Solution 0.02 16384 16384 2.087E+00 1.30 Dataset4 Problem Statement Solution 0.01 16384 16384 1.332E+00 1.88 Dataset5 Problem Statement Solution 0.001 16384 16384 1.628E-01 4.64
Problem "problem_902_L2_dblExt"

 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 0.1 1000 200 1.007E-01 0.02 Dataset2 Problem Statement Solution 0.01 1000 200 1.668E-02 0.02 Dataset3 Problem Statement Solution 0.001 1000 200 1.734E-03 0.10
Problem "problem_903_L2_dblExt"

 Problem Datasets Const # 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 Dataset1 Problem Statement Solution 100 1024 1024 8.695E+02 2.1 Dataset2 Problem Statement Solution 10 1024 1024 1.177E+02 9.8 Dataset3 Problem Statement Solution 1 1024 1024 1.279E+01 16.8 Dataset4 Problem Statement Solution 0.1 1024 1024 1.294E+00 52.1 Dataset5 Problem Statement Solution 0.01 1024 1024 1.295E-01 587.0

CASE STUDY SUMMARY
This case study solves sparse reconstruction problems from SPARCO toolbox using External Functions Tool of PSG and operator given by SPARCO toolbox for implicit working with matrices.
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.
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. These formulations are described in paper Boyko et al. (2011).
We solved problems included in SPARCO toolbox in so called “LASSO-O” formulation. “LASSO-O” minimizes L2-error of regression with adding to objective a regularization linear term which is equal to the sum of absolute values of variables. The regularization term is intended to “suppress" components with small values. To investigate property of solution we solved every problem with different weight of regularization linear term and calculated cardinality and max functions in optimal points. These problems can be easy solved by methods for unconstrained optimization.
SPARCO toolbox provides a set of operators to deal with data. Problems were solved in PSG MATLAB Environment with the PSG External Function subroutine to avoid generating full matrix and to save time and memory.
We reported performance of AORDA Portfolio Safeguard (PSG) 64 bit version conducted on PC with 2.83 MHz processor.
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).