Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO

Aude Hofleitner; Tarek Rabbani; Mohammad Rafiee; Laurent El Ghaoui; Alex Bayen

doi:10.3934/dcdss.2014.7.503

Article Contents

2014, Volume 7, Issue 3: 503-523. Doi: 10.3934/dcdss.2014.7.503

This issue Previous Article Traffic light control: A case study Next Article Efficient robust control of first order scalar conservation laws using semi-analytical solutions

Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO

1.
Electrical Engineering and Computer Science, UC Berkeley
2.
Mechanical Engineering, UC Berkeley
3.
Electrical Engineering and Computer Science, Civil and Environmental Engineering, UC Berkeley

Received: April 30, 2013

Revised: July 31, 2013

Published: May 2014

Abstract Related Papers Cited by

Abstract

The LASSO is a widely used shrinkage and selection method for linear regression. We propose a generalization of the LASSO in which the $l_1$ penalty is applied on a linear transformation of the regression parameters, allowing to input prior information on the structure of the problem and to improve interpretability of the results. We also study time varying system with an $l_1$-penalty on the variations of the state, leading to estimates that exhibit few ``jumps''. We propose a homotopy algorithm that updates the solution as additional measurements are available. The algorithm takes advantage of the sparsity of the solution for computational efficiency and is promising for mining large datasets. The algorithm is implemented on three experimental data sets representing applications to traffic estimation from sparsely sampled probe vehicles, flow estimation in tidal channels and text analysis of on-line news.

Keywords:

Mathematics Subject Classification: Primary: 49M30, 68W27; Secondary: 68U99.

Citation:

Related Papers

Cited by

References

[1]	J. Anderson and M. Mierzwa, An introduction to the Delta Simulation Model II (DSM2) for simulation of hydrodynamics and water quality of the Sacramento-San Joaquin Delta, in Office of State Water Project Planning, California Department of Water Resources, 2002.
[2]	F. Bach, R. Jenatton, J. Mairal and G. Obozinski, Convex optimization with sparsity-inducing norms, in Optimization for Machine Learning, 2011, 19-53.
[3]	R. Baraniuk, Compressive sensing, IEEE Signal. Proc. Mag., 24 (2007), 118.doi: 10.1109/CISS.2008.4558479.
[4]	A. Bayen, J. Butler and A. Patire, et al., Mobile Millennium, Final Report, Tech. rep., University of California, Berkeley, UCB-ITS-CWP-2011-6, 2011.
[5]	D. Bertsekas, Incremental gradient, subgradient, and proximal methods for convex optimization: A survey, Optimization for Machine Learning, (2011), 85 pp.
[6]	E. Candès, Compressive sampling, Congress of Mathematicians, 3 (2006), 1433-1452.
[7]	V. Chow, Open-channel Hydraulics, McGraw-Hill Book Company, New York, NY, 1988.
[8]	J. Cunge, F. Holly and A. Verwey, Practical Aspects of Computational River Hydraulics, Pitman, 1980.
[9]	I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics, 57 (2004), 1413-1457.doi: 10.1002/cpa.20042.
[10]	Y. Dodge, Statistical Data Analysis Based on the $l_1$-Norm and Related Methods, Birkhäuser Verlag, Basel, 2002.doi: 10.1007/978-3-0348-8201-9.
[11]	I. Drori and D. Donoho, Solution of $l_1$ minimization problems by LARS/homotopy methods, in International Conference on Acoustics, Speech and Signal Processing, Vol. 3, IEEE, 2006.doi: 10.1109/ICASSP.2006.1660734.
[12]	B. Efron, T. Hastie, I. Johnstone and R. Tibshirani, Least angle regression, Ann. Statist., 32 (2004), 407-451.doi: 10.1214/009053604000000067.
[13]	M. Figueiredo and R. Nowak, A bound optimization approach to wavelet-based image deconvolution, in International Conference on Image Processing, Vol. 2, IEEE, 2005.doi: 10.1109/ICIP.2005.1530172.
[14]	M. Figueiredo, R. Nowak and S. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE Journal of selected topics in signal processing, 1 (2008), 586-597.doi: 10.1109/JSTSP.2007.910281.
[15]	J. Friedman, T. Hastie, H. Höfling and R. Tibshirani, Pathwise coordinate optimization, Ann. Appl. Stat., 1 (2007), 302-332.doi: 10.1214/07-AOAS131.
[16]	J. Fuchs, On sparse representations in arbitrary redundant bases, IEEE Transactions on Information Theory, 50 (2004), 1341-1344.doi: 10.1109/TIT.2004.828141.
[17]	P. Garrigues and L. El Ghaoui, An homotopy algorithm for the Lasso with online observations, in Neural Information Processing Systems, 21, 2008.
[18]	B. Gawalt, J. Jia, L. Miratrix, L. El Ghaoui, B. Yu and S. Clavier, Discovering word associations in news media via feature selection and sparse classification, in Proceedings of the International Conference on Multimedia Information Retrieval, ACM, New York, NY, 2010, 211-220.doi: 10.1145/1743384.1743421.
[19]	G. Golub and C. Van Loan, Matrix Computations, Third edition, Johns Hopkins University Press, Baltimore, MD, 1996.
[20]	I. Guyon and A. Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3 (2003), 1157-1182.
[21]	A. Hofleitner, R. Herring, P. Abbeel and A. Bayen, Learning the dynamics of arterial traffic from probe data using a Dynamic Bayesian Network, IEEE Transactions on Intelligent Transportation Systems, 13 (2012), 1679-1693.doi: 10.1109/TITS.2012.2200474.
[22]	A. Hofleitner, T. Rabbani, L. El Ghaoui and A. Bayen, Online homotopy algorithm for a generalization of the LASSO, IEEE Transactions on Automatic Control, 58 (2013), 3175-3179.doi: 10.1109/TAC.2013.2259373.
[23]	T. Hunter, T. Moldovan, M. Zaharia, S. Merzgui, J. Ma, M. J. Franklin, P. Abbeel and A. M. Bayen, Scaling the Mobile Millennium system in the cloud, in Proceedings of the 2nd ACM Symposium on Cloud Computing, Article No. 28, ACM, New York, NY, 2011, 1-8.doi: 10.1145/2038916.2038944.
[24]	S. Kim, K. Koh, S. Boyd and D. Gorinevsky, $l_1 $ trend filtering, SIAM Rev., 51 (2009), 339-360.doi: 10.1137/070690274.
[25]	S. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, An Interior-Point Method for Large-Scale $l_1$-Regularized Least Squares, IEEE Journal of Selected Topics in Signal Processing, 1 (2008), 606-617.
[26]	K. Knight and W. Fu, Asymptotics for lasso-type estimators, Annals of Statistics, 28 (2000), 1356-1378.doi: 10.1214/aos/1015957397.
[27]	H. Lee, A. Battle, R. Raina and A. Ng, Efficient sparse coding algorithms, Advances in Neural Information Processing Systems, 19 (2007), 801 pp.
[28]	X. Litrico and V. Fromion, Boundary control of linearized Saint-Venant equations oscillating modes, Automatica, 42 (2006), 967-972.doi: 10.1016/j.automatica.2006.02.002.
[29]	X. Litrico and V. Fromion, Modeling and Control of Hydrosystems, Springer, 2009.doi: 10.1007/978-1-84882-624-3.
[30]	X. Litrico and V. Fromion, Frequency modeling of open-channel flow, ASCE Journal of Journal of Hydraulic Engineering, 130 (2004), 806-815.doi: 10.1061/(ASCE)0733-9429(2004)130:8(806).
[31]	I. Loris, On the performance of algorithms for the minimization of $l_1$-penalized functionals, Inverse Problems, 25 (2009), 035008, 16 pp.doi: 10.1088/0266-5611/25/3/035008.
[32]	J. Mairal and B. Yu, Complexity analysis of the Lasso regularization path, in International Conference on Machine Learning, 2012.
[33]	A. Ng, Feature selection, $l_1$ vs. $l_2$ regularization, and rotational invariance, in 21st International Conference on Machine learning, ACM, 2004, 78 pp.
[34]	M. Osborne, B. Presnell and B. Turlach, A new approach to variable selection in least squares problems, IMA journal of numerical analysis, 20 (2000), 389-403.doi: 10.1093/imanum/20.3.389.
[35]	S. Rosset and J. Zhu, Piecewise linear regularized solution paths, The Annals of Statistics, 35 (2007), 1012-1030.doi: 10.1214/009053606000001370.
[36]	M. Salman Asif and J. Romberg, Dynamic Updating for $l_1$ regularization, IEEE Journal of Selected Topics in Signal Processing, 4 (2010), 421-434.
[37]	R. Tibshirani, Regression shrinkage and selection via the Lasso, Journal of the Royal Statistical Society. Series B (Methodological), 58 (1996), 267-288.
[38]	H. Zou and T. Hastie, Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67 (2005), 301-320.doi: 10.1111/j.1467-9868.2005.00503.x.