Properties and refinements of the fused Lasso. (English) Zbl 1173.62027

Rinaldo, Alessandro

Ann. Stat. 37, No. 5B, 2922-2952 (2009).

Summary: We consider estimating an unknown signal, both blocky and sparse, which is corrupted by additive noise. We study three interrelated least squares procedures and their asymptotic properties. The first procedure is the fused Lasso, put forward by J. Friedman et al. [Ann. Appl. Stat. 1, No. 2, 302–332 (2007; Zbl 1378.90064)], which we modify into a different estimator, called the fused adaptive Lasso, with better properties. The other two estimators we discuss solve least squares problems on sieves; one constrains the maximal \(\ell _{1}\) norm and the maximal total variation seminorm, and the other restricts the number of blocks and the number of non-zero coordinates of the signal. We derive conditions for the recovery of the true block partition and the true sparsity patterns by the fused Lasso and the fused adaptive Lasso, and we derive convergence rates for the sieve estimators, explicitly in terms of the constraining parameters.

MSC:

62G08	Nonparametric regression and quantile regression
62G20	Asymptotic properties of nonparametric inference
65C60	Computational problems in statistics (MSC2010)

Keywords:

fused Lasso; consistency; sieve least squares

Citations:

Zbl 1378.90064

Software:

ftnonpar

References:

[1]	Birman, M. S. and Solomjak, M. Z. (1967). Piece-wise polynomial approximations of functions in the class W p \alpha . Mat. Sb. ( N.S. ) 73 295-317.
[2]	Boysen, L., Kempe, A., Liebscher, V., Munk, A. and Wittich, Ol. (2009). Consistencies and rates of convergence of jump-penalized least squares estimators. Ann. Statist. 37 157-183. · Zbl 1155.62034 · doi:10.1214/07-AOS558
[3]	Caselles, V., Chambolle, A. and Novaga, M. (2007). The discontinuity set of solutions of the TV denoising problem and some extensions. Multiscale Model. Simul. 6 879-894. · Zbl 1145.49024 · doi:10.1137/070683003
[4]	Davies, P. L. and Kovac, A. (2001a). Local extremes, runs, strings and multiresolution. Ann. Statist. 29 1-48. With discussion and rejoinder by the authors. · Zbl 1029.62038 · doi:10.1214/aos/996986501
[5]	Davies, P. L. and Kovac, A. (2001b). Local extremes, runs, strings and multiresolution. Ann. Statist. 29 61-65. · Zbl 1029.62038 · doi:10.1214/aos/996986501
[6]	DeVore, R. A. (1998). Nonlinear approximation. Acta Numerica 7 51-150. · Zbl 0931.65007
[7]	Dobson, D. C. and Vogel, C. R. (1997). Convergence of an iterative method for total variation denoising. SIAM J. Numer. Anal. 34 1779-1791. JSTOR: · Zbl 0898.65034 · doi:10.1137/S003614299528701X
[8]	Donoho, D. L. and Johnstone, I. M. (1994). Minimax risk over \ell p -balls for \ell q -error. Probab. Theory Related Fields 99 277-303. · Zbl 0802.62006 · doi:10.1007/BF01199026
[9]	Friedman, J., Hastie, T., Höfling, H. and Tibshirani, R. (2007). Pathways coordinate optimization. Ann. Appl. Stat. 1 302-332. · Zbl 1378.90064 · doi:10.1214/07-AOAS131
[10]	Greenshtein, E. (2006). Best subset selection, persistence in high-dimensional statistical learning and optimization under l 1 constraint. Ann. Statist. 34 2367-2386. · Zbl 1106.62022 · doi:10.1214/009053606000000768
[11]	Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces : Isoperimetry and Processes 23 . Springer, Berlin. · Zbl 0748.60004
[12]	Lorentz, G. G., Golitschek, M. V. and Makovoz, Y. (1996). Constructive Approximation : Advanced Problems. Grundlehren der Mathematischen Wissenschaften [ Fundamental Principles of Mathematical Sciences ] 304 . Springer, Berlin. · Zbl 0910.41001
[13]	Loubes, J. M. and van de Geer, S. (2002). Adaptive estimation in regression, using soft thresholding type penalties. Statistica Neerlandica 56 454-479. · Zbl 1090.62534
[14]	Mammen, E. and van de Geer, S. (1997). Locally adaptive regression splines. Ann. Statist. 25 387-413. · Zbl 0871.62040 · doi:10.1214/aos/1034276635
[15]	Massart, P. (2007). Concentration Inequalities and Model Selection. Lecture Notes in Mathematics 1896 . Springer, Berlin. · Zbl 1170.60006 · doi:10.1007/978-3-540-48503-2
[16]	Rudin, L. I., Osher, S. and Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. Physica D 60 259-268. · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[17]	Stanley, R. P. (2000). Enumerative Combinatorics . Cambridge Univ. Press, Cambridge. · Zbl 0978.05002
[18]	van de Geer, S. (2000). Empirical Processes in M-Estimation . Cambridge Univ. Press, Cambridge. · Zbl 1179.62073
[19]	van de Geer, S. (2007). Oracle Inequalities and Regularization 191-252. European Mathematical Society, Zürich.
[20]	van der Vaart, A. W. and Wellner, J. A. (1996). Weak Convergence of Empirical Processes . Springer, New York. · Zbl 0862.60002
[21]	Wainwright, M. J. (2006). Sharp thresholds for high-dimensional and noisy recovery of sparsity. IEEE Trans. Info. Theory .
[22]	Zhao, P. and Yu, B. (2006). On model selection consistency of lasso. J. Mach. Learn. Res. 7 2541-2563. · Zbl 1222.62008