Penalized least squares

For $\lambda \ge 0$, a full-column-rank design matrix $B$, and a positive semidefinite matrix $\Omega$, minimize $\Vert y-B\beta {\Vert }^2+\lambda {\beta }^T\Omega \beta$. Differentiation gives $(B^{T}B+\lambda \Omega )\hat{\beta }=B^{T}y$. The fitted-value matrix is $B(B^{T}B+\lambda \Omega {)}^{-1}{B}^T$, whose trace measures the effective degrees of freedom.

A penalized least-squares estimator balances squared error with a nonnegative penalty $J$. The Lasso uses the coefficient ${\ell }_1$ norm; graph total variation denoising uses the ${\ell }_1$ norm of endpoint differences. The choice of normalization of the squared loss changes the numerical tuning parameter.

For the identity design and $y={\theta }^{\ast }+z$, comparing the minimizing objective at $\hat{\theta }$ with its value at ${\theta }^{\ast }$ and expanding the squared Euclidean norm proves the displayed inequality, with $h=\hat{\theta }-{\theta }^{\ast }$. This deterministic inequality does not assume any probability distribution for the noise. A bound on the noise inner product turns it into a statistical error estimate.