Case Study: Sparse Signal Reconstruction: a Cardinality Approach

Back to main page

Case study background and problem formulations

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

PROBLEM 1: problem_constr_cardinality
Minimize Meanabs_pen (minimizing L1-error of regression)
subject to
Cardn ≤ Const1 (constraint on cardinality of the solution vector)
Box constraints (bounds on variables)
——————————————————————–
Meanabs_pen = Mean Absolute Penalty
Cardn = Cardinality
Box constraints = constraints on individual decision variables
——————————————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset1 4096 1024 0 8.07
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data
Download other datasets in Run-File Environment.
Instructions for importing problems from Run-File to PSG MATLAB.

Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec)
Dataset2 Problem Statement Data Solution 4096 1024 0.0000999 13.71
PROBLEM 2: problem_minimize_cardinality
Minimize Cardn (minimizing cardinality of the solution vector)
subject to
Meanabs_pen ≤ Const2 (constraint on L1-error of regression)
Box constraints (bounds on variables)
——————————————————————–
Cardn = Cardinality
Meanabs_pen = Mean Absolute Penalty
Box constraints = constraints on individual decision variables
——————————————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset1 4096 1024 160 900.08
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data
Download other datasets in Run-File Environment.
Instructions for importing problems from Run-File to PSG MATLAB.

Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec)
Dataset2 Problem Statement Data Solution 4096 1024 160 900.24
PROBLEM 3: problem_constr_polynomabs
Minimize Meanabs_pen (minimizing L1-error of regression)
subject to
Polynom_abs ≤ Const3 (constraint on the sum of absolute values of the solution vector)
Box constraints (bounds on variables)
——————————————————————–
Meanabs_pen = Mean Absolute Penalty
Polynom_abs = Polynomial Absolute
Box constraints = constraints on individual decision variables
——————————————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset1 4096 1024 0 6.16
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data
Download other datasets in Run-File Environment.
Instructions for importing problems from Run-File to PSG MATLAB.

Problem Datasets # of Variables # of Scenarios Objective Value Solving Time, PC 2.66GHz (sec)
Dataset2 Problem Statement Data Solution 4096 1024 0.00009836 9.89
Download Problem Data for CPLEX

Dataset1 Problem Data for CPLEX
CASE STUDY SUMMARY
This case study suggests an approach for Signal Sparse Reconstruction using nonconvex formulations with cardinality functions counting number of nonzero elements in a vector. Three formulated problems are special cases of a broad family of approaches known as Compressive Sensing. Problem 1 minimizes L1-error of regression subject to a constraint on cardinality of the solution vector; Problem 2 minimizes cardinality of the solution vector subject to a constraint on L1-error of regression; Problem 3 minimizes L1-error of regression subject to constraint on the sum of absolute values of the solution vector. This case study optimizes a problem described in paper Wright et al. (2007). The approach and the computation results are described in more detail in paper Boyko et al. (2011).
Each of the 3 problems is solved using 2 datasets:
• Dataset1 for no noise data;
• Dataset2 for including noise.
Case study also includes dataset for solving Sparse Reconstruction problem with noise using CPLEX.
References
• Figueiredo, M., Nowak, R. and S. Wright (2007): Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. Selected Topics in Signal Processing, IEEE Journal of, vol. 1, no. 4, pp. 586–597.
• Boyko, N., Karamemis, G., Kuzmenko, V. and S. Uryasev (2011): Sparse Signal Reconstruction: a Cardinality Approach. Submitted for publication (download Sparse_Signal_Reconstruction_Cardinality_Approach.pdf ).