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

Back to main page
Case study background and problem formulations

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)
——————————————————————–
Quadratic = External Quadratic Penalty Function
Box constraints = constraints on individual decision variables
——————————————————————–

Problem “problem_2_L2_dblExt”

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 https://epubs.siam.org/doi/abs/10.1137/S003614450037906X
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

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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)

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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)

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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)

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
Sources of Data

Candes, E., Romberg, J.: L1-magic. http://www.l1-magic.org/ (2007)

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
Sources of Data

Candes, E., Romberg, J.: L1-magic. http://www.l1-magic.org/(2007)

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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 https://epubs.siam.org/doi/abs/10.1137/S003614450037906X
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

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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 https://epubs.siam.org/doi/abs/10.1137/S003614450037906X
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

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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)

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
Sources of Data

Database of Creative Commons licensed sounds: URL https://freesound.org/

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
Sources of Data

Database of Creative Commons licensed sounds: URL https://freesound.org/

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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)

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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).

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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).

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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 https://library.seg.org/doi/abs/10.1190/1.2148142
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 https://academic.oup.com/gji/article-abstract/173/1/233/554282

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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”
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

Problem Datasets			Const	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 2.66GHz (sec)
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
Timing: Data_loading_time = 11.97, Preprocessing_time = 0.69, Solving_time = 272.61
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 the publication).