Dantzig Selector with an Approximately Optimal Denoising Matrix and its Application in Sparse Reinforcement Learning

Bo Liu Auburn University, Luwan Zhang, Ji Liu
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:78-87, 2016.

Abstract

Dantzig Selector (DS) is widely used in compressed sensing and sparse learning for feature selection and sparse signal recovery. Since the DS formulation is essentially a linear programming optimization, many existing linear programming solvers can be simply applied for scaling up. The DS formulation can be explained as a basis pursuit denoising problem, wherein the data matrix (or measurement matrix) is employed as the denoising matrix to eliminate the observation noise. However, we notice that the data matrix may not be the optimal denoising matrix, as shown by a simple counter-example. This motivates us to pursue a better denoising matrix for defining a general DS formulation. We first define the optimal denoising matrix through a minimax optimization, which turns out to be an NP-hard problem. To make the problem computationally tractable, we propose a novel algorithm, termed as “Optimal” Denoising Dantzig Selector (ODDS), to approximately estimate the optimal denoising matrix. Empirical experiments validate the proposed method. Finally, a novel sparse reinforcement learning algorithm is formulated by extending the proposed ODDS algorithm to temporal difference learning, and empirical experimental results demonstrate to outperform the conventional "vanilla" DS-TD algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-university16c, title = {Dantzig Selector with an Approximately Optimal Denoising Matrix and its Application in Sparse Reinforcement Learning}, author = {University, Bo Liu Auburn and Zhang, Luwan and Liu, Ji}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {78--87}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/university16c/university16c.pdf}, url = {https://proceedings.mlr.press/r14/university16c.html}, abstract = {Dantzig Selector (DS) is widely used in compressed sensing and sparse learning for feature selection and sparse signal recovery. Since the DS formulation is essentially a linear programming optimization, many existing linear programming solvers can be simply applied for scaling up. The DS formulation can be explained as a basis pursuit denoising problem, wherein the data matrix (or measurement matrix) is employed as the denoising matrix to eliminate the observation noise. However, we notice that the data matrix may not be the optimal denoising matrix, as shown by a simple counter-example. This motivates us to pursue a better denoising matrix for defining a general DS formulation. We first define the optimal denoising matrix through a minimax optimization, which turns out to be an NP-hard problem. To make the problem computationally tractable, we propose a novel algorithm, termed as “Optimal” Denoising Dantzig Selector (ODDS), to approximately estimate the optimal denoising matrix. Empirical experiments validate the proposed method. Finally, a novel sparse reinforcement learning algorithm is formulated by extending the proposed ODDS algorithm to temporal difference learning, and empirical experimental results demonstrate to outperform the conventional "vanilla" DS-TD algorithm.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Dantzig Selector with an Approximately Optimal Denoising Matrix and its Application in Sparse Reinforcement Learning %A Bo Liu Auburn University %A Luwan Zhang %A Ji Liu %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-university16c %I PMLR %P 78--87 %U https://proceedings.mlr.press/r14/university16c.html %V R14 %X Dantzig Selector (DS) is widely used in compressed sensing and sparse learning for feature selection and sparse signal recovery. Since the DS formulation is essentially a linear programming optimization, many existing linear programming solvers can be simply applied for scaling up. The DS formulation can be explained as a basis pursuit denoising problem, wherein the data matrix (or measurement matrix) is employed as the denoising matrix to eliminate the observation noise. However, we notice that the data matrix may not be the optimal denoising matrix, as shown by a simple counter-example. This motivates us to pursue a better denoising matrix for defining a general DS formulation. We first define the optimal denoising matrix through a minimax optimization, which turns out to be an NP-hard problem. To make the problem computationally tractable, we propose a novel algorithm, termed as “Optimal” Denoising Dantzig Selector (ODDS), to approximately estimate the optimal denoising matrix. Empirical experiments validate the proposed method. Finally, a novel sparse reinforcement learning algorithm is formulated by extending the proposed ODDS algorithm to temporal difference learning, and empirical experimental results demonstrate to outperform the conventional "vanilla" DS-TD algorithm. %Z Reissued by PMLR on 04 October 2026.
APA
University, B.L.A., Zhang, L. & Liu, J.. (2016). Dantzig Selector with an Approximately Optimal Denoising Matrix and its Application in Sparse Reinforcement Learning. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:78-87 Available from https://proceedings.mlr.press/r14/university16c.html. Reissued by PMLR on 04 October 2026.

Related Material