4
$\begingroup$

The solution to the minimizing problem: $$RSS(f, \lambda) = \sum_{i=1}^n (y_i - f(x_i))^2 + \lambda \int (f''(t))^2 dt$$ is written in matrix form as $f = N\theta = \sum_{j = 1}^n N_j(x_i) \theta_j$ where the $N_j(x)$ are a $n$-dimensional set of basis functions representing a natural cubic spline. Together with a choice of $\lambda$ we have a smoothing spline with the estimate $$\hat f = S_\lambda y$$ where $$S_\lambda = N(N^tN + \lambda \Sigma_N)^{-1}N^t$$ and $\Sigma_{N_{ij}} = (\int N''_i(t)N''_j(t) dt)_{ij}$ and $N_{ij} = N_j(x_i)$.


Why is $\mathrm{Rank}(S_\lambda) = n$, or equivalently $N$ invertible?

$\endgroup$
38
  • 2
    $\begingroup$ My answer to a slightly different question at stats.stackexchange.com/a/180360/919 gives one explanation. Because $S_\lambda$ is recognizable as a "Ridge regression hat matrix," many other posts are also directly relevant. Note that $\lambda \gt 0$ is necessary to conclude $S_\lambda$ is of full rank. $\endgroup$
    – whuber
    Jan 4, 2023 at 15:25
  • 2
    $\begingroup$ Your notations are very confusing: "$N$" is used for denoting the number of observations and a matrix simultaneously. Could you please clarify that more clearly? $\endgroup$
    – Zhanxiong
    Jan 4, 2023 at 17:05
  • 2
    $\begingroup$ My explanation applies directly, with no additional reasoning required: $S_\lambda$ is the product of three matrices and all have rank $n:$ $N$ and $N^\prime$ by stipulation and $(N^\prime N + \lambda \Sigma_N)^{-1}$ due to its explicit expression as an inverse. $\endgroup$
    – whuber
    Jan 4, 2023 at 21:00
  • 1
    $\begingroup$ @Lejoon OK. But if so, why are you still asking the question "how do we know $N$ is invertible?" You are given that $N$ is invertible (if it is of full column rank). $\endgroup$
    – Zhanxiong
    Jan 4, 2023 at 21:17
  • 1
    $\begingroup$ @whuber That was what I thought. I said "$N$ is invertible" because I asked OP to confirm if "$N \in \mathbb{R}^{n \times p}$ is of full rank" is correct. He said yes "except $N$ is $n \times n$" (which probably turned out to be a false claim as you pointed out). If the problem is just to prove $\operatorname{rank}(S_\lambda) = p$, it is quite straightforward. $\endgroup$
    – Zhanxiong
    Jan 5, 2023 at 0:43

2 Answers 2

3
$\begingroup$

A spline is a method of fitting a function to a set of points $(x_1,y_1),$ $(x_2,y_2),$ $\ldots, (x_n,y_n).$ The answer to the question is because natural cubic splines exist.

The full explanation appears in the last two sentences of this post. The intervening material consists of standard definitions, constructions, and observations in linear algebra to establish notation and fix the concepts. It is included because (a) the comment thread to the question indicates there is a risk of misinterpreting some of the terminology and (b) taking this abstract approach will demonstrate we need to know only that splines exist, but we don't need any details of their construction. As such, the results are both easy to obtain and they apply to any kind of spline (in the extremely general sense defined below).

The vector space interpretation is also helpful for bringing to the fore two fundamental operations associated with splines: (i) using splines to approximate arbitrary functions and (ii) passing splines through finite sets of points. I will address these in turn, but wish to emphasize there's little to demonstrate and nothing to calculate.

Linear algebra

To set the stage, we will be working with functions $f:X\to \mathcal R$ defined on the set $X$ of all possible values of the data $x_i.$ The codomain is a field $\mathcal R$ (usually the real or complex numbers). The set of these functions, $\mathbb R^X,$ is naturally a vector space under pointwise addition of functions and scalar multiplication. That is, given any $x\in X,$ for all $f,g\in \mathcal R^X$ and $\alpha,\beta\in\mathcal R,$

$$(\alpha f+\beta g)(x) = \alpha f(x)+\beta g(x).$$

A spline is, first of all, a vector subspace $\mathbb G \subset \mathcal R^X:$ we intend to use the functions in $\mathbb G$ to approximate arbitrary functions in $\mathcal R^X.$

Any finite collection of distinct "knots" $\Xi=(\xi_1, \xi_2, \ldots, \xi_p)\in X^p$ determines a linear transformation $\iota_\Xi: \mathcal R^X \to \mathcal R^\Xi$ via restriction to the domain $\Xi,$

$$\iota_\Xi(f)(\xi_j) = f_{|\Xi(\xi_j)} = f(\xi_j)$$

for $j= 1, 2, \ldots, p.$ The codomain $\mathcal R^\Xi$ is canonically isomorphic to the standard $p$-dimensional vector space $\mathcal R^p:$ simply write the function $\iota_\Xi(f)$ as the vector $\mathbf y = (f(\xi_1),f(\xi_2),\ldots,f(\xi_p)).$ I will therefore treat these as the same vector space without further comment.

The image $\iota_\Xi(\mathbb G) \subset \mathcal R^\Xi$ is the set of values that spline functions can take on $\Xi.$ The assertion "splines exist" means that whenever $\Xi$ is a sequence of knots, $\iota_{\Xi}$ is a surjection: to every possible set of values $\mathbf y = (y_1,y_2,\ldots, y_p),$ there is a spline function $f\in\mathbb G$ attaining those values at the knots.

The foregoing characterizes a spline as a function space $\mathbb G$ with an existence property. I am not aware of any such characterization in the literature, but believe it applies to every type of spline that has been invented.

Existence is usually proven by exhibiting a right inverse for arbitrary $\iota_\Xi.$ That is, given $\mathbf y,$ a function $g\in\mathbb G$ is constructed for which $\iota_\Xi(g) = \mathbf y.$ This chapter of ESL includes several such constructions for natural cubic splines defined on real numbers $X=\mathbb R,$ so I take the existence as not in question here.

Let $\iota_\Xi^*$ be such a right inverse: that is, $\iota_\Xi^*$ is a vector space isomorphism between $\mathcal R^p$ and a subspace of $\mathbb G$ where, for all $\mathbf y \in \mathcal R^p,$

$$\iota_\Xi(\iota_\Xi^*(\mathbf y)) = \mathbf y.$$

Because $\iota_\Xi$ is an isomorphism, any basis $\mathcal E$ of $\mathcal R^p$ (that is, a linearly independent spanning subset) corresponds to a basis $\iota_\Xi^*(\mathcal E)$ of the image. The latter is what ESL means by a basis of spline functions. As we have seen, these really are functions and it really is a basis of a special finite-dimensional subspace of functions.

The circumstances of the question

That's it for the linear algebra preliminaries. Next, let's address the unstated assumptions of the question. These are

  1. $N$ is the matrix determined by a spline with "knots at the data values."

  2. The $x_i$ are distinct.

These indicate the matrix $N$ in the question is a special one where $p=n$ (assumption (1)) and the data values $x_i$ are the knots $\xi_i$ (which must be distinct, assumption (2)).

Pick any basis $\mathcal E = (\mathbf e_1, \ldots, \mathbf e_n).$ Each $\mathbf e_j = (e_{ij}, j = 1, \ldots, n)$ is an $n$-vector. The matrix $N$ in the question is constructed from the $n$ knots $\Xi \subset \mathcal R^X$ and the basis $\mathcal E \in \left(\mathcal R^n\right)^n$ by applying each of the corresponding basis spline functions to the data:

$$N = (n_{ij}) = \iota_\Xi^*(\mathbf e_j)(x_i) = \iota_\Xi^*(\mathbf e_j)(\xi_i) = (e_{ij}).\tag{*}$$

(In the notation of the question, the basis functions are $N_j = \iota_\Xi^*(\mathbf e_j)$ and $N = (n_{ij}) = N_j(x_i).$)

Solution

The identity $(*)$ shows $N$ is a square $n\times n$ matrix equal to the matrix of $\mathcal E.$ Because $\mathcal E$ is linearly independent, this matrix has rank $n$ and so does its transpose. Equivalently, $N$ is invertible.

The question concerns the rank of a matrix of the form

$$S_\lambda = N^\prime A_\lambda^{-1} N.$$

The interior matrix in this product is invertible (its inverse is $A_\lambda$). Because natural cubic splines exist, $N$ is invertible, whence $S_\lambda$ (which represents a composition of three invertible linear transformations) also is invertible and therefore must have the same rank $n$ as its components, QED.

$\endgroup$
2
  • $\begingroup$ Thank you @whuber. Just checking if I've understood correctly, should it be: "The codomain \mathcal R^\Xi is canonically isomorphic to the standard $\mathcal R^n$." or $\mathcal R^p$? $\endgroup$
    – Lejoon
    Jan 9, 2023 at 8:45
  • 1
    $\begingroup$ Thank you for the close reading -- you are correct. I'll fix that typo right away. $\endgroup$
    – whuber
    Jan 9, 2023 at 14:26
2
$\begingroup$

This is a partial answer to be completed, I posted it just for clarification and drawing more attention.

I have consulted the ESL section. Let me first clarify the notations. The problem is 1D function estimation so the training data is $(x_i, y_i): i = 1, \ldots, n$ (as I pointed out in the comment, using $N$ to denote the number of observations is an unfortunate confusion, even in ESL the spline matrix is boldfaced. So here I will still use $n$ to denote the number of observations). The spline matrix $N$ is defined as \begin{align} N = \begin{bmatrix} N_1(x_1) & N_2(x_1) & \cdots & N_n(x_1) \\ N_1(x_2) & N_2(x_2) & \cdots & N_n(x_2) \\ \vdots & \vdots & \ddots & \vdots \\ N_1(x_n) & N_2(x_n) & \cdots & N_n(x_n) \end{bmatrix}. \tag{1} \end{align} Evidently, if $x_i = x_j$ for some $i \neq j$, then clearly $N$ is not invertible (because then the $i$-th row and the $j$-th row are identical). So in order $\operatorname{rank}(S_\lambda) = n$ (a claim made by ESL, p.153), $x_1, \ldots, x_n$ must be distinct (without loss of generality, assume $x_1 < x_2 < \cdots < x_n$).

According to the author:

$N_j(x)$ are an $n$-dimensional set of basis functions for representing this family of natural splines...

By calling $\{N_1(x), \ldots, N_n(x)\}$ "basis functions" (to be fair, doing so without first proving they really formed a basis of a vector space -- which was not clearly stated in advance, is loose), they are necessarily linearly independent in the vector space $V$ of spline functions (known as "spline space", more accurately, given knots $x_1 < x_2 < \cdots < x_n$ and only cubic splines are under consideration, I think $V$ is a real vector space spanned by $\{1, x, x^2, x^3, (x - x_1)_+^3, \ldots, (x - x_n)_+^3\}$). As you are interested in, this statement, of course requires a mathematical proof, which the text omitted.

Recall $N_j(x)$ is defined as (Equation (5.4) in ESL): \begin{align} N_1(x) = 1, N_2(x) = x, N_{k + 2}(x) = d_k(x) - d_{n - 1}(x), k = 1, \ldots, n - 2, \tag{2} \end{align}
where \begin{align} d_k(x) = \frac{(x - x_k)_+^3 - (x - x_n)_+^3}{x_n - x_k}. \tag{3} \end{align}

Plug $(2)$ and $(3)$ into $(1)$, then $\det(N)$ (denoted by $D_n$) is \begin{align} & D_n = \begin{vmatrix} 1 & x_1 & 0 & 0 &\cdots & 0 \\ 1 & x_2 & (x_2 - x_1)^3/(x_n - x_1) & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n - 1} & (x_{n - 1} - x_1)^3/(x_n - x_1) & (x_{n - 1} - x_2)^3/(x_n - x_2) & \cdots & (x_{n - 1} - x_{n - 2})^3/(x_n - x_{n - 2}) \\ 1 & x_n & (x_n - x_1)^2 - (x_n - x_{n - 1})^2 & (x_n - x_2)^2 - (x_n - x_{n - 1})^2 & \cdots & (x_n - x_{n - 2})^2 - (x_n - x_{n - 1})^2 \end{vmatrix} \\ & ???? \neq 0. \end{align}

When $n = 1, 2, 3$, \begin{align} & D_1 = 1 \neq 0, \\ & D_2 = x_2 - x_1 \neq 0, \\ & D_3 = 2(x_2 - x_1)^2(x_3 - x_2) \neq 0, \end{align} all confirming $N$ is invertible. However, for $n \geq 4$, it is more difficult to make a conclusion. I have calculated \begin{align} D_4 &= (x_4 - x_1)^{-1}(x_2 - x_1)(x_3 - x_2)^2(x_2 + x_3 - 2x_1)(2x_4 - x_2 - x_3) \\ &+ (x_4 - x_2)^{-1}(x_2 - x_1)(x_3 - x_2)^3[(x_1 - x_2)^2 + (x_3 - x_4)^2 - (x_4 - x_1)^2], \end{align} but it is not immediate to see if $D_4 \neq 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.