# Case Study: Sparse Signal Reconstruction: a Cardinality Approach

** 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 |

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 |

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 |

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 upproch 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 incuding noise.

• Dataset1 for no noise data;

• Dataset2 for incuding 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 ).