Sparse Solutions to the Least-Squares Problems using LASSO

Sparse models gives insights that people otherwise wouldn't have.

Let's say x is feature vector and d is label, and we want to have an inner product such that 

And A is the Xi Transpose vectors, and Al contains the lth feature component and the features is over the sum ai. If Wl = 0, this means that Al is unimportant.

If only a small number of Wl are nonzero, then we can know that only these few features actully matter!

One way of finding sparse solution is to count the number of nonzero elements. This is sometimes called the l0 norm. The symbol "1" implies 1 when wi not equal to zero and 0 when wi = 0.

We can find W with the minimum number of elements subject the the square error bounded by epsilon.

This is intractable computationally, since we have to search through all possible elements of w. The is because the problem is non-convex. 

It turns I can use a convex relaxation to obtain a tractable problem with minimizations. We can try to get the minimum of the difference. LASSO, or the Least Absolute Selection & Shrinkage Operator, is convex and tends to consider sparse solutions. 

Going up the bowl graph is increasing the constant C. |w1| + |w2| = C, which represents the equation for a line. The other quadrants have to change the signs of w1 and w2 respectively.

The "corners" of ||w1|| often indicates sparse solutions. The 1-norm ball has these corners and encourage sparse solutions.

What about minimizing the 2-norm? The 2norm is w1^2 + w2^2 = Constant, so this is a circle, so we tend to get non-sparse solutions for 2-norm. 

LASSO is a regularized least squared problem, and we can try to minimize the squared error plus the lambda multiplied by the one-norm. The equation is in the below picture. 

LASSO is based on the L1 norm, and Ridge regression is based on L2 norm. LASSO tends to produce a sparse solution, whereas ridge regression has an nonsparse solution. LASSO tends to have small model error, whereas ridge regression tends to produce a great amount of prediction error. We can't solve LASSO in close form, but we can solve ridge regression in closed form. 

Oftentimes, LASSO is used for model and feature selection, and we minimize the L1 squared error, and identify the indices which the solution has nonzero coefficients.

Once features are selected, Debiasing is used to form a model.  We can resolve for new model weights to minimize the error using the only features that were selected in the feature selector step. This eliminates the shrinkage in the norm.