TY - GEN
T1 - Three structural results on the lasso problem
AU - Xu, Pingmei
AU - Ramadge, Peter J.
PY - 2013/10/18
Y1 - 2013/10/18
N2 - The lasso problem, least squares with a ℓ1 regularization penalty, has been very successful as a tool for obtaining sparse representations of data in terms of given dictionary. It is known, but not widely appreciated, that the lasso problem need not have a unique solution. Sufficient conditions which ensure uniqueness of the solution are known but necessary and sufficient conditions have been elusive. We present three structural results on the lasso problem. First, we show that when the dictionary has more columns than rows, it is always possible to ensure that the dictionary has full row rank. Next we show that the feasible set for the dual lasso problem is bounded if and only if the dictionary has full row rank. Lastly, we give necessary and sufficient conditions for the uniqueness of a lasso solution.
AB - The lasso problem, least squares with a ℓ1 regularization penalty, has been very successful as a tool for obtaining sparse representations of data in terms of given dictionary. It is known, but not widely appreciated, that the lasso problem need not have a unique solution. Sufficient conditions which ensure uniqueness of the solution are known but necessary and sufficient conditions have been elusive. We present three structural results on the lasso problem. First, we show that when the dictionary has more columns than rows, it is always possible to ensure that the dictionary has full row rank. Next we show that the feasible set for the dual lasso problem is bounded if and only if the dictionary has full row rank. Lastly, we give necessary and sufficient conditions for the uniqueness of a lasso solution.
KW - Bounded
KW - Dual Problem
KW - Lasso
KW - Necessary and Sufficient Conditions
KW - Uniqueness
UR - http://www.scopus.com/inward/record.url?scp=84890507384&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84890507384&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2013.6638287
DO - 10.1109/ICASSP.2013.6638287
M3 - Conference contribution
AN - SCOPUS:84890507384
SN - 9781479903566
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 3392
EP - 3396
BT - 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings
T2 - 2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013
Y2 - 26 May 2013 through 31 May 2013
ER -