# American Institute of Mathematical Sciences

• Previous Article
$\mathcal{L}_{∞}$-norm computation for large-scale descriptor systems using structured iterative eigensolvers
• NACO Home
• This Issue
• Next Article
Unbounded state-dependent sweeping processes with perturbations in uniformly convex and q-uniformly smooth Banach spaces
March  2018, 8(1): 97-117. doi: 10.3934/naco.2018006

## Fused LASSO penalized least absolute deviation estimator for high dimensional linear regression

 1 Community Health Center, Beijing Jiaotong University, Beijing 100044, China 2 Department of Mathematics and Statistics, Loyola University Maryland, Baltimore, MD 21210, USA 3 Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, China

* Corresponding author: Lingchen Kong

This paper was prepared at the occasion of The 10th International Conference on Optimization: Techniques and Applications (ICOTA 2016), Ulaanbaatar, Mongolia, July 23-26,2016, with its Associate Editors of Numerical Algebra, Control and Optimization (NACO) being Prof. Dr. Zhiyou Wu, School of Mathematical Sciences, Chongqing Normal University, Chongqing, China, Prof. Dr. Changjun Yu, Department of Mathematics and Statistics, Curtin University, Perth, Australia, and Shanghai University, China, and Prof. Gerhard-Wilhelm Weber, Middle East Technical University, Ankara, Turkey

Received  January 2017 Revised  December 2017 Published  March 2018

Fund Project: The work was supported in part by National Natural Science Foundation of China (11671029), and the Fundamental Research Funds for the Central Universities (2016JBM081).

The least absolute shrinkage and selection operator (LASSO) has been playing an important role in variable selection and dimensionality reduction for high dimensional linear regression under the zero-mean or Gaussian assumptions of the noises. However, these assumptions may not hold in practice. In this case, the least absolute deviation is a popular and useful method. In this paper, we focus on the least absolute deviation via Fused LASSO, called Robust Fused LASSO, under the assumption that the unknown vector is sparsity for both the coefficients and its successive differences. Robust Fused LASSO estimator does not need any knowledge of standard deviation of the noises or any moment assumptions of the noises. We show that the Robust Fused LASSO estimator possesses near oracle performance, i.e. with large probability, the $\ell_2$ norm of the estimation error is of order $O(\sqrt{k(\log p)/n})$. The result is true for a wide range of noise distributions, even for the Cauchy distribution. In addition, we apply the linearized alternating direction method of multipliers to find the Robust Fused LASSO estimator, which possesses the global convergence. Numerical results are reported to demonstrate the efficiency of our proposed method.

Citation: Yanqing Liu, Jiyuan Tao, Huan Zhang, Xianchao Xiu, Lingchen Kong. Fused LASSO penalized least absolute deviation estimator for high dimensional linear regression. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 97-117. doi: 10.3934/naco.2018006
##### References:

show all references

##### References:
Results of RFLASSO when $i = 2, \sigma = 0.001$
Results of FLASSO when $i = 2, \sigma = 0.001$
Results for RFLASSO when $i = 2, \sigma = 0.001$
Results for FLASSO when $i = 2, \sigma = 0.001$
Iterative scheme of LADMM algorithm for RFLASSO
 LADMM Algorithm for RFLASSOInput: $X$ , $Y$ , $\tau$ , $\lambda_1>0, \lambda_2>0, \mu>0, \nu>0$ and $\eta>\rho(\mu X^TX+\nu A^TA)$ , where $\rho(\cdot)$ denotes the spectral radius.Select $(\beta^0, \gamma^0, \tau^0, \alpha^0, \theta^0)=(1, 1, 1, 1, 1)$ ; For $k=1, 2, \cdots, n$        Do            Compute $\beta^{k+1}$ by (23),            Compute $\gamma^{k+1}$ by (24),            Compute $\tau^{k+1}$ by (25),            Update $\alpha^{k+1}=\alpha^k-\nu(A\beta^{k+1}-\gamma^{k+1})$ ,            Update $\theta^{k+1}=\theta^k-\mu(y-X\beta^{k+1}-\tau^{k+1})$ . End Output: $(\beta^n, \gamma^n, \tau^n, \alpha^n, \theta^n)$ as an approximate solution of (3).
 LADMM Algorithm for RFLASSOInput: $X$ , $Y$ , $\tau$ , $\lambda_1>0, \lambda_2>0, \mu>0, \nu>0$ and $\eta>\rho(\mu X^TX+\nu A^TA)$ , where $\rho(\cdot)$ denotes the spectral radius.Select $(\beta^0, \gamma^0, \tau^0, \alpha^0, \theta^0)=(1, 1, 1, 1, 1)$ ; For $k=1, 2, \cdots, n$        Do            Compute $\beta^{k+1}$ by (23),            Compute $\gamma^{k+1}$ by (24),            Compute $\tau^{k+1}$ by (25),            Update $\alpha^{k+1}=\alpha^k-\nu(A\beta^{k+1}-\gamma^{k+1})$ ,            Update $\theta^{k+1}=\theta^k-\mu(y-X\beta^{k+1}-\tau^{k+1})$ . End Output: $(\beta^n, \gamma^n, \tau^n, \alpha^n, \theta^n)$ as an approximate solution of (3).
$\rho(0.5X^TX+0.5A^TA)$ for design matrix with unit column norms
 i 1 2 3 4 $\sigma=0.001$ 5.246 5.289 5.324 5.344 $\sigma=0.005$ 5.265 5.296 5.333 5.35 $\sigma=0.01$ 5.273 5.301 5.342 5.356
 i 1 2 3 4 $\sigma=0.001$ 5.246 5.289 5.324 5.344 $\sigma=0.005$ 5.265 5.296 5.333 5.35 $\sigma=0.01$ 5.273 5.301 5.342 5.356
The results for RFLASSO with size $(n, p, g) = (360i, 1280i, 160i)$
 i $\sigma$ Iter CPU Obj Error $i=1$ $\sigma=0.001$ 156 0.424 31.052 20.3164 $\sigma=0.005$ 165 0.430 32.276 23.3330 $\sigma=0.01$ 175 0.463 33.364 23.5509 $i=2$ $\sigma=0.001$ 150 1.783 48.669 24.9877 $\sigma=0.005$ 168 1.953 59.415 25.5110 $\sigma=0.01$ 189 2.113 67.510 31.8536 $i=3$ $\sigma=0.001$ 169 4.268 87.465 33.2984 $\sigma=0.005$ 154 4.307 96.761 37.3335 $\sigma=0.01$ 167 4.109 91.263 34.8521 $i=4$ $\sigma=0.001$ 166 7.525 123.087 40.0416 $\sigma=0.005$ 167 7.382 132.316 41.0560 $\sigma=0.01$ 157 6.833 137.114 44.1079
 i $\sigma$ Iter CPU Obj Error $i=1$ $\sigma=0.001$ 156 0.424 31.052 20.3164 $\sigma=0.005$ 165 0.430 32.276 23.3330 $\sigma=0.01$ 175 0.463 33.364 23.5509 $i=2$ $\sigma=0.001$ 150 1.783 48.669 24.9877 $\sigma=0.005$ 168 1.953 59.415 25.5110 $\sigma=0.01$ 189 2.113 67.510 31.8536 $i=3$ $\sigma=0.001$ 169 4.268 87.465 33.2984 $\sigma=0.005$ 154 4.307 96.761 37.3335 $\sigma=0.01$ 167 4.109 91.263 34.8521 $i=4$ $\sigma=0.001$ 166 7.525 123.087 40.0416 $\sigma=0.005$ 167 7.382 132.316 41.0560 $\sigma=0.01$ 157 6.833 137.114 44.1079
Selected results for RFLASSO and FLASSO
 RFLASSO FLASSO $\sharp{\{~|\widehat{\beta}_i|<0.1, ~i\in G^c}\}$ 2240 2240 $\text{max}_{i\in G^c}|\widehat{\beta}_i|$ 0.0147 0.0153 $\sharp{\{~|\widehat{\beta}_i-\beta^*_i|<0.1, ~i\in G}\}$ 320 320 $\text{max}_{i\in G}|\widehat{\beta}_i-\beta^*_i|$ 0.1447 0.1365
 RFLASSO FLASSO $\sharp{\{~|\widehat{\beta}_i|<0.1, ~i\in G^c}\}$ 2240 2240 $\text{max}_{i\in G^c}|\widehat{\beta}_i|$ 0.0147 0.0153 $\sharp{\{~|\widehat{\beta}_i-\beta^*_i|<0.1, ~i\in G}\}$ 320 320 $\text{max}_{i\in G}|\widehat{\beta}_i-\beta^*_i|$ 0.1447 0.1365
Selected results for RFLASSO and FLASSO
 RFLASSO FLASSO $\sharp{\{~|\widehat{\beta}_i|<0.1, ~i\in G^c}\}$ 2240 2372 $\text{max}_{i\in G^c}|\widehat{\beta}_i|$ 0.0442 0.0997 $\sharp{\{~|\widehat{\beta}_i-\beta^*_i|<0.1, ~i\in G}\}$ 320 188 $\text{max}_{i\in G}|\widehat{\beta}_i-\beta^*_i|$ 0.1329 1.7218
 RFLASSO FLASSO $\sharp{\{~|\widehat{\beta}_i|<0.1, ~i\in G^c}\}$ 2240 2372 $\text{max}_{i\in G^c}|\widehat{\beta}_i|$ 0.0442 0.0997 $\sharp{\{~|\widehat{\beta}_i-\beta^*_i|<0.1, ~i\in G}\}$ 320 188 $\text{max}_{i\in G}|\widehat{\beta}_i-\beta^*_i|$ 0.1329 1.7218
 [1] Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247 [2] Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037 [3] Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078 [4] Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917 [5] Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1783-1799. doi: 10.3934/jimo.2019029 [6] Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030 [7] Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047 [8] Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 [9] Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067 [10] Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016 [11] Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317 [12] Wei Xue, Wensheng Zhang, Gaohang Yu. Least absolute deviations learning of multiple tasks. Journal of Industrial & Management Optimization, 2018, 14 (2) : 719-729. doi: 10.3934/jimo.2017071 [13] Zhifeng Dai, Huan Zhu, Fenghua Wen. Two nonparametric approaches to mean absolute deviation portfolio selection model. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2283-2303. doi: 10.3934/jimo.2019054 [14] Yifan Xia, Yongchao Hou, Xin He, Shaogao Lv. Learning rates for partially linear functional models with high dimensional scalar covariates. Communications on Pure & Applied Analysis, 2020, 19 (8) : 3917-3932. doi: 10.3934/cpaa.2020172 [15] Peng Zhang. Multiperiod mean semi-absolute deviation interval portfolio selection with entropy constraints. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1169-1187. doi: 10.3934/jimo.2016067 [16] Editorial Office. RETRACTION: Peng Zhang, Chance-constrained multiperiod mean absolute deviation uncertain portfolio selection. Journal of Industrial & Management Optimization, 2019, 15 (2) : 537-564. doi: 10.3934/jimo.2018056 [17] Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077 [18] Shaoyong Lai, Qichang Xie. A selection problem for a constrained linear regression model. Journal of Industrial & Management Optimization, 2008, 4 (4) : 757-766. doi: 10.3934/jimo.2008.4.757 [19] Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103 [20] Junying Hu, Xiaofei Qian, Jun Pei, Changchun Tan, Panos M. Pardalos, Xinbao Liu. A novel quality prediction method based on feature selection considering high dimensional product quality data. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021099

Impact Factor: