1.3 LASSO and matching pursuit

Motivation

A regression model may contain many candidate features even though a useful description needs only a few of them. Least squares measures the quality of the fitted responses, but it does not directly express a preference for using fewer features. LASSO introduces a coefficient penalty whose corner at zero can remove some coefficients exactly. Matching pursuit approaches sparse approximation through a different decision: choose one useful direction at a time and record what remains unexplained.

These ideas share residuals and correlations, but they solve different mathematical problems. A small residual certifies a good fit to the observed response. A LASSO solution must additionally balance that fit against its coefficient penalty. A greedy sequence can be understood by inspecting each update, whereas a global minimizer needs an optimality condition involving every feature. Keeping these conditions separate makes each method easier to calculate and interpret.

Feature scaling is part of the model. Replacing one column by a large multiple allows its coefficient to become correspondingly smaller without changing its contribution to the fitted response. An absolute coefficient penalty therefore depends on the units used for the features. Centering and scaling selected from the training observations give the penalty a definite meaning; the same transformation is then applied to later observations.

Definitions

Definition

The LASSO objective

Let $A=[a_1,\ldots,a_p]\in\mathbb R^{n\times p}$ be a fixed feature matrix, $y\in\mathbb R^n$ a response vector, and $\lambda>0$. We minimize

$$F_\lambda(\beta)=\frac12\|y-A\beta\|_2^2+\lambda\|\beta\|_1, \qquad \|\beta\|_1=\sum_{j=1}^p|\beta_j|.$$

The residual is $r=y-A\beta$. In this definition every coefficient is penalized.

The factor $1/2$ determines the threshold that will appear below. Removing it while keeping the same numerical $\lambda$ changes the problem. Likewise, dividing the squared loss by the number of observations changes the relative strength of a fixed penalty. An unpenalized intercept is a separate parameter: its stationarity condition is $\mathbf1^Tr=0$, and its coefficient is not put through a threshold. The examples here have no extra intercept.

The function is convex because both terms are convex. Since $F_\lambda(\beta)\ge\lambda\|\beta\|_1$, it grows without bound as the coefficient vector grows without bound, so a minimizer exists. Independent columns make the squared loss strictly convex and hence give uniqueness. Dependent columns do not justify a general uniqueness claim.

Definition

Dictionary atoms and a pursuit state

In a pursuit calculation the nonzero columns $a_j$ are called atoms. A state consists of coefficients $\beta$ and a residual satisfying $r=y-A\beta$. Ordinary matching pursuit starts at $\beta=0$, $r=y$, and repeatedly adds a multiple of one atom. An atom may be selected again.

Theorem/proposition

Proposition

LASSO optimality through residual correlations

A vector $\beta$ minimizes $F_\lambda$ exactly when, for every $j$,

$$\begin{aligned} \beta_j\ne0&\Longrightarrow a_j^Tr=\lambda\operatorname{sign}(\beta_j),\\ \beta_j=0&\Longrightarrow |a_j^Tr|\le\lambda. \end{aligned}$$

Thus a zero coefficient is compatible with an interval of correlations, rather than requiring the corresponding correlation to vanish.

Proposition

Soft thresholding for orthonormal features

If $A^TA=I_p$ and $z=A^Ty$, the unique LASSO minimizer is

$$\beta_j=S_\lambda(z_j),\qquad S_\lambda(t)=\operatorname{sign}(t)\max(|t|-\lambda,0).$$

Here $S_\lambda(0)=0$. Correlations with magnitude at most $\lambda$ produce zero coefficients; larger magnitudes are reduced by $\lambda$.

Proposition

Exact energy decrease in an ordinary matching-pursuit step

For a nonzero atom $a_j$ and current residual $r$, the multiple minimizing $\|r-\alpha a_j\|_2^2$ is $\alpha=(a_j^Tr)/\|a_j\|_2^2$. The new residual obeys

$$\|r-\alpha a_j\|_2^2 =\|r\|_2^2-\frac{(a_j^Tr)^2}{\|a_j\|_2^2}, \qquad a_j^T(r-\alpha a_j)=0.$$

The greatest one-step decrease comes from maximizing the displayed quotient. For unit atoms this is equivalent to maximizing $|a_j^Tr|$.

The first condition also identifies where an entire coefficient vector becomes zero. At $\beta=0$ the residual is $y$, so all zero-coordinate conditions hold exactly when $\lambda\ge\max_j|a_j^Ty|$. This gives a useful starting value for examining a range of penalties. As the penalty is decreased below that level, the zero vector ceases to satisfy at least one correlation condition. The condition describes the chosen training problem; selecting a penalty for prediction still requires evaluating models on observations excluded from their fitting calculations. It is not determined by the number of zero coefficients alone.

The interval at zero is essential to this behavior. For a squared coefficient penalty the derivative at zero is a single value, whereas the absolute value can balance a whole interval of nonzero loss gradients. This explains why thresholding is a structural feature of the penalty, rather than a numerical rounding rule applied after a dense fit has been computed.

Proof sketch or proof idea

The gradient of the squared-loss term with respect to $\beta_j$ is $-a_j^Tr$. For a positive coefficient the derivative of $|\beta_j|$ is $1$; for a negative coefficient it is $-1$. At zero its supporting slopes form $[-1,1]$. The convex optimality condition is consequently $0\in-A^Tr+\lambda\partial\|\beta\|_1$, which gives the first proposition. Convexity makes this condition sufficient as well as necessary: a zero supporting slope means that moving to any other vector cannot lower the objective.

For orthonormal columns, expansion separates the coordinates:

$$F_\lambda(\beta) =\frac12(\|y\|_2^2-\|z\|_2^2) +\sum_{j=1}^p\left(\frac12(\beta_j-z_j)^2+\lambda|\beta_j|\right).$$

For one coordinate $t$, a positive minimizer must satisfy $t-z+\lambda=0$, which lies on the positive side only if $z>\lambda$. A negative minimizer must satisfy $t-z-\lambda=0$, which lies on the negative side only if $z<-\lambda$. In the remaining interval the left derivative at zero is nonpositive and the right derivative is nonnegative, so zero minimizes the coordinate function. This derives all three cases, including the boundaries.

Finally, expand an ordinary pursuit step as $\|r\|_2^2-2\alpha a_j^Tr+\alpha^2\|a_j\|_2^2$ and complete the square. The positive coefficient $\|a_j\|_2^2>0$ gives a unique minimizing increment. Substitution proves the energy identity and orthogonality to the chosen atom. Neither statement requires the other atoms to be orthogonal to that atom.

Worked examples

Worked example

Example 1: A coefficient disappears at the threshold

Take $A=I_2$, $y=(3,-1)^T$, and $\lambda=1$. The correlations are the response entries, so soft thresholding gives

$$\beta=(2,0)^T,\qquad r=(1,-1)^T,\qquad F_1(\beta)=3.$$

Indeed, the squared-loss term is $(1^2+(-1)^2)/2=1$ and the penalty is $2$. The first residual correlation equals $1$, as required for a positive coefficient. The second equals $-1$, which belongs to the permitted interval for a zero coefficient. Equality at its endpoint does not force that coefficient to be negative.

The zero vector has objective $5$, while the unpenalized fit $\beta=y$ has objective $4$. The minimizer lies between these choices by balancing fit and coefficient size. If $\lambda=1/2$ instead, the solution is $(5/2,-1/2)^T$; its objective is $1/4+3/2=7/4$. These are different objectives, so their numerical minima are not a common measure for selecting $\lambda$.

Worked example

Example 2: An atom is useful more than once

Let $a_1=(1,0)^T$, $a_2=(1,1)^T/\sqrt2$, and $y=(0,1)^T$. Both atoms have unit length. Initially the correlations are $0$ and $1/\sqrt2$, so the first step selects $a_2$. After three ordinary matching-pursuit steps we obtain

$$\begin{array}{c|c|c|c} k&j&\beta^T&r^T\\ 0&-& (0,0)&(0,1)\\ 1&2&(0,1/\sqrt2)&(-1/2,1/2)\\ 2&1&(-1/2,1/\sqrt2)&(0,1/2)\\ 3&2&(-1/2,3/(2\sqrt2))&(-1/4,1/4) \end{array}$$

The squared residual norms are $1$, $1/2$, $1/4$, and $1/8$. At the second step the increment on $a_1$ is $-1/2$. It removes the first residual coordinate but makes the residual correlated with $a_2$ again. The third increment on $a_2$ is $1/(2\sqrt2)$, which must be added to its existing coefficient. Overwriting that coefficient would break $r=y-A\beta$.

Worked example

Example 3: Refitting the selected span changes the answer

After selecting the two atoms above, orthogonal matching pursuit refits both coefficients jointly by least squares. Solving $\beta_1+\beta_2/\sqrt2=0$ and $\beta_2/\sqrt2=1$ gives

$$\beta_{\mathrm{OMP}}=(-1,\sqrt2)^T,\qquad r_{\mathrm{OMP}}=0.$$

Ordinary matching pursuit after two steps instead has coefficients $(-1/2,1/\sqrt2)^T$ and squared residual norm $1/4$. Refitting uses the whole selected span; it is not another name for subtracting the newest atom.

Exact fitting also differs from LASSO optimality. With $\lambda=1/4$, the OMP vector has $F_{1/4}=(1+\sqrt2)/4$. The two-step MP vector has $F_{1/4}=1/4+\sqrt2/8$, which is smaller despite its nonzero residual. This comparison does not certify the MP vector as a LASSO solution; it shows why a residual-only stopping argument cannot certify that objective.

Coordinate updates and greedy updates

For a general feature matrix, the orthonormal soft-threshold formula does not apply to all coordinates simultaneously. There is nevertheless an exact one-coordinate update for a nonzero column $a_j$. Hold the other coefficients fixed and define $r_{-j}=r+a_j\beta_j$. This adds back the current contribution of feature $j$, leaving the response that this coordinate is allowed to explain. Minimizing $\|r_{-j}-a_jt\|_2^2/2+\lambda|t|$ gives

$$\beta_j^{\mathrm{new}} =\frac{S_\lambda(a_j^Tr_{-j})}{\|a_j\|_2^2}, \qquad r^{\mathrm{new}}=r-a_j(\beta_j^{\mathrm{new}}-\beta_j).$$

This updates an entire coefficient. Penalizing only a proposed increment by $\lambda|\alpha|$ defines a different one-step objective when the atom has already been used: the global penalty involves $|\beta_j+\alpha|$. Residual correlations can verify the LASSO conditions after a computation, independently of the algorithm used to obtain its coefficients.

To see why the denominator has this form, put $c=\|a_j\|_2^2>0$ and $\rho=a_j^Tr_{-j}$. Up to a term independent of $t$, the coordinate objective is $ct^2/2-\rho t+\lambda|t|$. The positive and negative stationary equations are $ct=\rho-\lambda$ and $ct=\rho+\lambda$ respectively, with zero filling the interval between them. Each coordinate subproblem is therefore strictly convex even if the full feature matrix has dependent columns. For a zero column the coefficient is set directly to zero by minimizing its penalty.

A pursuit residual whose correlations vanish for every atom is already perpendicular to the entire available feature space. It then satisfies the ordinary least-squares normal equations, even when its length is positive: the unexplained component lies outside that space. Before that stage, the energy identity measures a possible improvement. In Example 2 the successive energies keep halving, so approaching an exact representation does not require reaching it in finitely many ordinary MP steps. A prescribed number of steps selects a point in this sequence; it is a separate modelling choice from selecting the coefficient penalty in LASSO.

The following code traces the ordinary pursuit in Example 2. It chooses by the energy decrease, so the expression remains correct for non-unit atoms.

import numpy as np

A = np.array([[1.0, 1.0 / np.sqrt(2.0)],
              [0.0, 1.0 / np.sqrt(2.0)]])
y = np.array([0.0, 1.0])
beta = np.zeros(2)
residual = y.copy()
norm2 = np.sum(A * A, axis=0)
for step in range(3):
    correlation = A.T @ residual
    j = int(np.argmax(correlation ** 2 / norm2))
    increment = correlation[j] / norm2[j]
    beta[j] += increment
    residual -= increment * A[:, j]
    energy = float(residual @ residual)
    print(f"{step + 1}: atom={j + 1}, beta=({beta[0]:.6f}, {beta[1]:.6f}), energy={energy:.6f}")
omp, _, _, _ = np.linalg.lstsq(A, y, rcond=None)
assert np.allclose(omp, [-1.0, np.sqrt(2.0)])

1: atom=2, beta=(0.000000, 0.707107), energy=0.500000
2: atom=1, beta=(-0.500000, 0.707107), energy=0.250000
3: atom=2, beta=(-0.500000, 1.060660), energy=0.125000

Penalized pursuit increments

A pursuit step can penalize the amount added to a coefficient. To derive this version, use a squared loss without the factor $1/2$ and define

$$\widetilde F_\lambda(\beta)=\|y-A\beta\|_2^2+\lambda\|\beta\|_1 =2F_{\lambda/2}(\beta),\qquad\lambda>0.$$

This normalization has threshold $\lambda/2$. Starting with $\beta=0$ and $r=y$, choose a nonzero atom, write $\kappa_j=\|a_j\|_2^2>0$ and $u_j=a_j^Tr$, and minimize the one-variable increment objective

$$q_j(\gamma)=\|r-a_j\gamma\|_2^2+\lambda|\gamma| =\|r\|_2^2-2u_j\gamma+\kappa_j\gamma^2+\lambda|\gamma|.$$

The residual in this expression is the current residual: the old contribution of the chosen atom has not been added back. The penalized quantity is the new increment, not the entire updated coefficient.

Proposition

A penalized increment and its exact local improvement

The unique minimizing increment is

$$\gamma_j^*=\frac{S_{\lambda/2}(u_j)}{\kappa_j} =\begin{cases} (u_j-\lambda/2)/\kappa_j,&u_j>\lambda/2,\\ 0,&|u_j|\le\lambda/2,\\ (u_j+\lambda/2)/\kappa_j,&u_j<-\lambda/2. \end{cases}$$

Its local objective improvement is

$$\Delta_j=q_j(0)-q_j(\gamma_j^*) =\frac{\bigl(\max(|u_j|-\lambda/2,0)\bigr)^2}{\kappa_j}.$$

On the positive side, differentiating gives $2\kappa_j\gamma-2u_j+\lambda=0$; that candidate is positive only when $u_j>\lambda/2$. The negative-side equation gives the opposite branch. At zero, the supporting-slope interval contains zero exactly when $|u_j|\le\lambda/2$. Substituting the consistent branch into the expanded quadratic proves the improvement formula. Comparing only the two nonzero stationary expressions would miss this interval.

For example, with $a_j=1$, $r=1/2$, and $\lambda=2$, the correct increment is zero and $q_j(0)=1/4$. The expressions $3/2$ and $-1/2$ lie outside their respective sign branches; their objective values are $4$ and $2$. Neither replaces the zero solution.

Choosing the largest $\Delta_j$ gives the greatest decrease in this local increment objective. For unit atoms, or any common positive $\kappa_j$, selecting a largest $|u_j|$ also maximizes $\Delta_j$. Unequal norms require the displayed denominator. If all scores vanish, every proposed increment is zero. After selecting an atom, preserve the pursuit invariant by

$$\beta_j\leftarrow\beta_j+\gamma_j^*,\qquad r^{\mathrm{new}}=r-a_j\gamma_j^*,\qquad \gamma_j^*\ne0\Longrightarrow a_j^Tr^{\mathrm{new}}=\frac{\lambda}{2}\operatorname{sign}(\gamma_j^*).$$

Repeated selections accumulate; the coefficient is not overwritten. Unlike ordinary MP, a nonzero penalized step leaves a threshold-sized correlation with its selected atom, rather than making that correlation zero.

For a concrete unequal-norm comparison, take $r=(2,2)^T$, atoms $a=(10,0)^T$ and $b=(1,1)^T$, and $\lambda=2$. Their raw correlations are $20$ and $4$, but the respective improvements are $361/100$ and $9/2$. Thus the larger raw correlation gives the smaller local improvement. The score compares the atoms in their specified scales; normalizing columns also requires interpreting the coefficient penalty in the new units.

The global penalty change is $\lambda(|\beta_j+\gamma|-|\beta_j|)$, whereas $q_j$ charges $\lambda|\gamma|$. Writing $e_j$ for the $j$th coordinate unit vector, the triangle inequality therefore gives

$$\widetilde F_\lambda(\beta+\gamma_j^*e_j) -\widetilde F_\lambda(\beta) \le q_j(\gamma_j^*)-q_j(0)=-\Delta_j.$$

Thus a correctly minimized increment cannot increase the global objective. The two changes agree for a previously unused coefficient, but need not agree after reuse. In particular, $\Delta_j$ is not generally the exact global improvement. If an increment shrinks an existing coefficient without crossing zero, its global penalty decreases while the increment penalty is positive. The inequality makes $\Delta_j$ a lower bound on the global decrease; maximizing it optimizes the local score, not necessarily the actual global decrease. Full coordinate minimization instead adds back the old contribution and replaces the entire coefficient:

$$\beta_j^{\mathrm{new}} =\frac{S_{\lambda/2}(u_j+\kappa_j\beta_j)}{\kappa_j}.$$

Worked example

Example 4: Penalized increments can stall before LASSO optimality

Use the unit-column matrix and response

$$A=\begin{pmatrix}1&3/5\\0&4/5\end{pmatrix},\qquad y=(3,1)^T,\qquad\lambda=2.$$

The initial correlations are $(3,13/5)^T$, so the first step selects atom 1. The next correlations are $(1,7/5)^T$, so atom 2 is selected next. The trace records increments as well as accumulated coefficients:

$$\begin{array}{c|c|c|c|c} k&j&\gamma&\beta^T&r^T\\ 0&-&-&(0,0)&(3,1)\\ 1&1&2&(2,0)&(1,1)\\ 2&2&2/5&(2,2/5)&(19/25,17/25)\\ 3&2&0&(2,2/5)&(19/25,17/25) \end{array}$$

After step 2, the correlations are $(19/25,1)^T$. Both scores vanish; the largest-correlation rule selects atom 2 again and produces zero. However, the positive first coefficient requires correlation $1$ for $\widetilde F_2$ optimality, not $19/25$. Full coordinate minimization would set $\beta_1=44/25$, already decreasing the objective by $36/625$.

The actual global solution is $(13/8,5/8)^T$, with residual $(1,1/2)^T$. Both positive-coordinate correlations equal $1$, verifying its optimality. Its objective is $23/4$, below the stalled value $146/25$. These values are $5/4+9/2$ and $26/25+24/5$, respectively: squared residual norm plus coefficient penalty. Since the two columns are independent, the verified global minimizer is unique for this particular matrix. The example separates decreasing an increment objective from minimizing a full coordinate: even a zero-improvement stopping state can fail the global coefficient conditions.

Constraints and smooth penalties

Let $\beta_\lambda$ minimize LASSO and set $\tau=\|\beta_\lambda\|_1$. It also minimizes the squared loss over $\|\beta\|_1\le\tau$. Otherwise a feasible vector with smaller loss would have no larger penalty, contradicting penalized optimality. This constructs a constrained problem from a particular penalized solution. It does not establish a one-to-one relation between $\lambda$ and $\tau$; several penalty values can give the same zero solution.

A smooth alternative replaces the absolute value by a rounded function. One normalized Huber penalty is

$$h_\delta(t)=\begin{cases} t^2/(2\delta),&|t|\le\delta,\\ |t|-\delta/2,&|t|>\delta, \end{cases}\qquad\delta>0.$$

Its outer slope is one and $h_\delta(t)\to|t|$ as $\delta\to0$. A normalized pseudo-Huber penalty provides another rounding:

$$p_\delta(t)=\sqrt{t^2+\delta^2}-\delta,\qquad\delta>0.$$

The normalized derivatives make their smoothness precise:

$$h_\delta'(t)=\begin{cases} t/\delta,&|t|\le\delta,\\ \operatorname{sign}(t),&|t|>\delta, \end{cases} \qquad p_\delta'(t)=\frac{t}{\sqrt{t^2+\delta^2}},\qquad p_\delta''(t)=\frac{\delta^2}{(t^2+\delta^2)^{3/2}}>0.$$

At $t=\pm\delta$, the Huber first derivatives agree, but the second derivative changes from $1/\delta$ to zero. Thus Huber is continuously differentiable, not twice differentiable there. Pseudo-Huber is smooth everywhere. Both have curvature $1/\delta$ at zero and limiting outer slope of magnitude one. Using $\delta h_\delta$ or $\delta p_\delta$ instead multiplies the penalty contribution by $\delta$ at fixed $\lambda$; specify this scale together with the smoothing width.

For $\lambda>0$, consider $G(t)=(t-z)^2/2+\lambda h_\delta(t)$. Inside the quadratic region, $G'(t)=t-z+\lambda t/\delta=0$ gives $t=\delta z/(\delta+\lambda)$. It belongs to that region precisely when $|z|\le\delta+\lambda$. Outside it, the stationary equation is $t-z+\lambda\operatorname{sign}(t)=0$. Its consistent branch gives

$$t_*=\begin{cases} \delta z/(\delta+\lambda),&|z|\le\delta+\lambda,\\ z-\lambda\operatorname{sign}(z),&|z|>\delta+\lambda. \end{cases}$$

At $z=\pm(\delta+\lambda)$, both expressions give $t_*=\pm\delta$. The quadratic loss is strictly convex and the penalty is convex, so this stationary point is the unique global minimizer. For either smoothed penalty, the scalar objective has derivative $-z$ at zero. Its minimizer is therefore zero exactly when $z=0$, unlike LASSO's interval of exact zeros. Here the smoothing is applied to coefficients; replacing a residual loss by Huber defines a different regression objective.

Common mistakes

Common mistake

Treating correlation, refitting, and optimality as the same test

For non-unit atoms, the largest raw correlation need not give the greatest residual-energy decrease; divide its square by the atom's squared norm. An ordinary MP residual is perpendicular to the most recently selected atom, whereas an OMP least-squares residual is perpendicular to every selected column. Neither observation alone checks the LASSO penalty conditions on all columns.

Coefficient sparsity is also representation-dependent. Two highly related features may exchange their contributions while leaving fitted responses similar. A selected feature is part of a model with specified units and a specified penalty, rather than a conclusion about causation.

For an exact illustration, take $A=[1,1]$, response $y=3$, and $\lambda=1$. Writing $t=\beta_1+\beta_2$, the triangle inequality gives $|\beta_1|+|\beta_2|\ge|t|$. The scalar optimum is $t=2$, and every vector $(2-s,s)^T$ with $0\le s\le2$ attains the same objective $3$. Some of these vectors have one nonzero coefficient and others have two. The fitted response is the same throughout, while the feature representation is ambiguous. This is why coefficient uniqueness cannot be inferred simply from the use of an absolute-value penalty.

Summary

The corner of the absolute-value penalty permits exact zero coefficients. Soft thresholding makes that mechanism explicit for orthonormal features and for individual coordinate subproblems. Ordinary matching pursuit instead controls the change in residual energy one atom at a time. Refitting the selected span produces OMP, while testing all residual correlations against the penalty conditions checks LASSO optimality.

Exercises

Checkpoint

Exercise 1: Let $A=I_3$, $y=(2,-1/2,0)^T$, and $\lambda=1$. Find the LASSO coefficients, residual, and objective value.

Apply soft thresholding to every response entry, including the middle one.

Checkpoint

Exercise 2: For residual $r=(1,1)^T$, compare atoms $a=(10,0)^T$ and $b=(1,1)^T$. Which maximizes raw correlation, and which removes more squared residual energy?

Calculate the correlation squared divided by the squared atom norm.

Checkpoint

Exercise 3: In Example 2, compute the fourth MP increment, coefficients, and squared residual norm.

Start with residual $(-1/4,1/4)^T$ and compare its two correlations.

Checkpoint

Exercise 4: A scalar LASSO problem has $A=[1]$, $y=1/2$, and $\lambda=1$. Check the candidate coefficient $0$. What fails if one considers only nonzero stationary candidates?

The absolute value has an interval of supporting slopes at zero.

Checkpoint

Exercise 5: For $(t-z)^2/2+\lambda h_\delta(t)$, take $\delta=1/2$ and $\lambda=1$. Find the minimizers for $z=1/4$ and $z=3/2$. Compare the first with scalar LASSO.

The boundary between the two solution branches is $\delta+\lambda$.

Solutions

Solution · Exercise 1 solution

The coefficients are $(1,0,0)^T$ and the residual is $(1,-1/2,0)^T$. The objective is $(1+1/4)/2+1=13/8$. The residual correlations of the two zero coordinates lie inside $[-1,1]$.

Solution · Exercise 2 solution

The raw correlations are $10$ and $2$, but the energy decreases are $10^2/100=1$ and $2^2/2=2$. Atom $b$ removes the entire residual, whereas atom $a$ removes only its first coordinate. Normalizing the selection score avoids a preference caused merely by the atom's length.

Solution · Exercise 3 solution

The correlations are $-1/4$ with $a_1$ and zero with $a_2$, so the fourth increment is $-1/4$ on $a_1$. The coefficients become $(-3/4,3/(2\sqrt2))^T$ and the residual becomes $(0,1/4)^T$. Its squared norm is $1/16$.

Solution · Exercise 4 solution

At zero, $r=1/2$ and the correlation $1/2$ belongs to $[-1,1]$, so the convex optimality condition holds. The positive-side equation proposes $t=-1/2$, outside that side; the negative-side equation proposes $t=3/2$, outside its side. Those invalid candidates do not replace the zero case. The actual objective at zero is $1/8$.

Solution · Exercise 5 solution

The branch boundary is $3/2$. For $z=1/4$, the quadratic-region formula gives $t_*=(1/2)(1/4)/(3/2)=1/12$, which is inside $|t|\le1/2$. Scalar LASSO instead gives $S_1(1/4)=0$. For $z=3/2$, both formulas give $t_*=1/2$: the inner formula is $(1/2)(3/2)/(3/2)$ and the outer one is $3/2-1$. This checks the boundary as well as the nonzero effect of smoothing.

Related notes

Least squares and residuals develops the residual geometry used here. Model validation and ridge regression explains how a penalty is chosen and how a quadratic penalty changes fitting. SVD and principal components studies orthogonal directions in data. The course reading list groups the books for further study.