Capabilities are Vectors

Conceptualizing features as infinite-dimensional vectors lets us apply the instruments of linear algebra to an unlimited panorama of recent issues, from picture and geometry processing to curve becoming, gentle transport, and machine studying.

Stipulations: introductory linear algebra, introductory calculus, introductory differential equations.

---

Vectors are sometimes first launched as lists of actual numbers—i.e. the acquainted notation we use for factors, instructions, and extra.

You could recall that this illustration is just one instance of an summary vector house.
There are lots of different kinds of vectors, comparable to lists of complex numbers, graph cycles, and even magic squares.

Nevertheless, all of those vector areas have one factor in frequent: a finite variety of dimensions.
That’s, every form of vector may be represented as a group of (N) numbers, although the definition of “quantity” varies.

If any (N)-dimensional vector is basically a length-(N) record, we may additionally contemplate a vector to be a mapping from an index to a worth.

[begin{align*}
mathbf{v}_1 &= x
mathbf{v}_2 &= y
mathbf{v}_3 &= z
end{align*} iff mathbf{v} = begin{bmatrix}x y zend{bmatrix}]

What does this angle trace at as we improve the variety of dimensions?

In larger dimensions, vectors begin to look extra like features!

Countably Infinite Indices

After all, a finite-length vector solely specifies a worth at a restricted variety of indices.
May we as a substitute outline a vector that comprises infinitely many values?

Writing down a vector representing a perform on the pure numbers ((mathbb{N}))—or another countably infinite area—is easy: simply prolong the record indefinitely.

This vector may symbolize the perform (f(x) = x), the place (x in mathbb{N}).

Uncountably Infinite Indices

Many fascinating features are outlined on the actual numbers ((mathbb{R})), so will not be representable as a countably infinite vector.
Subsequently, we should make a bigger conceptual leap: not solely will our set of indices be infinite, it will likely be uncountably infinite.

Which means we are able to’t write down vectors as lists in any respect—it’s impossible to assign an integer index to every component of an uncountable set.
So, how can we write down a vector mapping a actual index to a sure worth?

Now, a vector actually is simply an arbitrary perform:

Exactly defining how and why we are able to symbolize features as infinite-dimensional vectors is the purview of practical evaluation.
On this publish, we gained’t try and show our ends in infinite dimensions: we are going to give attention to constructing instinct through analogies to finite-dimensional linear algebra.

---

Formally, a vector house is outlined by selecting a set of vectors (mathcal{V}), a scalar field (mathbb{F}), and a zero vector (mathbf{0}).
The sphere (mathbb{F}) is usually the actual numbers ((mathbb{R})), complicated numbers ((mathbb{C})), or a finite discipline such because the integers modulo a chief ((mathbb{Z}_p)).

Moreover, we should specify methods to add two vectors and methods to multiply a vector by a scalar.

[begin{align*}
(+) &: mathcal{V}timesmathcal{V}mapstomathcal{V}
(cdot) &: mathbb{F}timesmathcal{V} mapsto mathcal{V}
end{align*}]

To explain a vector house, our definitions should entail a number of vector house axioms.

A Purposeful Vector House

Within the following sections, we’ll work with the vector house of actual features.
To keep away from ambiguity, sq. brackets are used to indicate perform utility.

• The scalar discipline (mathbb{F}) is the actual numbers (mathbb{R}).
• The set of vectors (mathcal{V}) comprises features from (mathbb{R}) to (mathbb{R}).
• (mathbf{0}) is the zero perform, i.e. (mathbf{0}[x] = 0).

Including features corresponds to making use of the features individually and summing the outcomes.

This definition generalizes the standard element-wise addition rule—it’s like including the 2 values at every index.

[f+g = begin{bmatrix}f_1 + g_1 f_2 + g_2 vdots end{bmatrix}]

Multiplying a perform by a scalar corresponds to making use of the perform and scaling the outcome.

This rule equally generalizes element-wise multiplication—it’s like scaling the worth at every index.

[alpha f = begin{bmatrix}alpha f_1 alpha f_2 vdots end{bmatrix}]

Proofs

Given these definitions, we are able to now show all vital vector house axioms.
We are going to illustrate the analog of every property in (mathbb{R}^2), the acquainted vector house of two-dimensional arrows.

Subsequently, we’ve constructed a vector house of features!
^{It will not be instantly apparent why this result’s helpful, however bear with us by way of a couple of extra definitions—we are going to spend the remainder of this publish exploring highly effective methods arising from this angle.}

A Customary Foundation for Capabilities

Except specified in any other case, vectors are written down with respect to the commonplace foundation.
In (mathbb{R}^2), the usual foundation consists of the 2 coordinate axes.

Therefore, vector notation is shorthand for a linear mixture of the usual foundation vectors.

Above, we represented features as vectors by assuming every dimension of an infinite-length vector comprises the perform’s outcome for that index.
This building factors to a pure generalization of the usual foundation.

Identical to the coordinate axes, every commonplace foundation perform comprises a (1) at one index and (0) in every single place else.
Extra exactly, for each (alpha in mathbb{R}),

[mathbf{e}_alpha[x] = start{circumstances} 1 & textual content{if } x = alpha 0 & textual content{in any other case} finish{circumstances}]

We will then categorical any actual perform (f) as a linear mixture of those foundation features:

[begin{align*} f[x] &= f[alpha]mathbf{e}_alpha[x] &= f[1]mathbf{e}_1[x] + f[2]mathbf{e}_2[x] + f[pi]mathbf{e}_pi[x] + dots finish{align*}]

When you consider this sum at (x), you’ll discover that every one phrases are zero—besides (mathbf{e}_x), making the outcome (f[x]).

---

Now that we are able to manipulate features as vectors, let’s begin transferring the instruments of linear algebra to the practical perspective.

One ubiquitous operation on finite-dimensional vectors is reworking them with matrices.
A matrix (mathbf{A}) encodes a linear transformation, which means multiplication preserves linear mixtures.

[mathbf{A}(alpha mathbf{x} + beta mathbf{y}) = alpha mathbf{A}mathbf{x} + beta mathbf{A}mathbf{y}]

Multiplying a vector by a matrix may be intuitively interpreted as defining a brand new set of coordinate axes from the matrix’s column vectors.
The result’s a linear mixture of the columns:

When all vectors may be expressed as a linear mixture of (mathbf{u}), (mathbf{v}), and (mathbf{w}), the columns kind a foundation for the underlying vector house.
Right here, the matrix (mathbf{A}) transforms a vector from the (mathbf{uvw}) foundation into the usual foundation.

Since features are vectors, we may think about reworking a perform by a matrix.
Such a matrix could be infinite-dimensional, so we are going to as a substitute name it a linear operator and denote it with (mathcal{L}).

[mathcal{L}f = begin{bmatrix} vert & vert & vert & mathbf{f} & mathbf{g} & mathbf{h} & cdots vert & vert & vert & end{bmatrix} begin{bmatrix}f_1 f_2 f_3 vdotsend{bmatrix} = f_1mathbf{f} + f_2mathbf{g} + f_3mathbf{h} + cdots] [begin{align*}
mathcal{L}f &= begin{bmatrix} vert & vert & vert & mathbf{f} & mathbf{g} & mathbf{h} & cdots vert & vert & vert & end{bmatrix} begin{bmatrix}f_1 f_2 f_3 vdotsend{bmatrix} &= f_1mathbf{f} + f_2mathbf{g} + f_3mathbf{h} + cdots
end{align*}]

This visualization isn’t very correct—we’re coping with uncountably infinite-dimensional vectors, so we are able to’t truly write out an operator in matrix kind.
Nonetheless, the construction is suggestive: every “column” of the operator describes a brand new foundation perform for our practical vector house.
Identical to we noticed with finite-dimensional vectors, (mathcal{L}) represents a change of foundation.

Differentiation

So, what’s an instance of a linear operator on features?
You would possibly recall that differentiation is linear:

[frac{partial}{partial x} left(alpha f[x] + beta g[x]proper) = alphafrac{partial f}{partial x} + betafrac{partial g}{partial x}]

It’s exhausting to visualise differentiation on basic features, however it’s possible for the subspace of polynomials, (mathcal{P}).
Let’s take a slight detour to look at this smaller house of features.

[mathcal{P} = { p[x] = a + bx + cx^2 + dx^3 + cdots }]

We sometimes write down polynomials as a sequence of powers, i.e. (1, x, x^2, x^3), and many others.
All polynomials are linear mixtures of the features (mathbf{e}_i[x] = x^i), so that they represent a countably infinite foundation for (mathcal{P}).

This foundation offers a handy vector notation:

[begin{align*} p[x] &= a + bx + cx^2 + dx^3 + cdots &= amathbf{e}_0 + bmathbf{e}_1 + c mathbf{e}_2 + dmathbf{e}_3 + dots finish{align*} iff mathbf{p} = start{bmatrix}a b c d vdotsend{bmatrix}] [begin{align*} p[x] &= a + bx + cx^2 + dx^3 + cdots &= amathbf{e}_0 + bmathbf{e}_1 + c mathbf{e}_2 + dmathbf{e}_3 + dots & iff mathbf{p} = start{bmatrix}a b c d vdotsend{bmatrix} finish{align*}]

Since differentiation is linear, we’re capable of apply the rule (frac{partial}{partial x} x^n = nx^{n-1}) to every time period.

[begin{align*}frac{partial}{partial x}p[x] &= vphantom{Biggvert}afrac{partial}{partial x}1 + bfrac{partial}{partial x}x + cfrac{partial}{partial x}x^2 + dfrac{partial}{partial x}x^3 + dots &= b + 2cx + 3dx^2 + cdots &= bmathbf{e}_0 + 2cmathbf{e}_1 + 3dmathbf{e}_2 + dotsend{align*} iff frac{partial}{partial x}mathbf{p} = start{bmatrix}b 2c 3d vdotsend{bmatrix}] [begin{align*}frac{partial}{partial x}p[x] &= vphantom{Biggvert}afrac{partial}{partial x}1 + bfrac{partial}{partial x}x + cfrac{partial}{partial x}x^2, + & phantom{=} dfrac{partial}{partial x}x^3 + dots &= b + 2cx + 3dx^2 + cdots &= bmathbf{e}_0 + 2cmathbf{e}_1 + 3dmathbf{e}_2 + dots &iff frac{partial}{partial x}mathbf{p} = start{bmatrix}b 2c 3d vdotsend{bmatrix}finish{align*}]

We’ve carried out a linear transformation on the coefficients, so we are able to symbolize differentiation as a matrix!

[frac{partial}{partial x}mathbf{p} = begin{bmatrix}0 & 1 & 0 & 0 & cdots 0 & 0 & 2 & 0 & cdots 0 & 0 & 0 & 3 & cdots vdots & vdots & vdots & vdots & ddots end{bmatrix}begin{bmatrix}a b c d vdotsend{bmatrix} = begin{bmatrix}b 2c 3d vdotsend{bmatrix}]

Every column of the differentiation operator is itself a polynomial, so this matrix represents a change of foundation.

[frac{partial}{partial x} = begin{bmatrix} vert & vert & vert & vert & vert & 0 & 1 & 2x & 3x^2 & 4x^3 & cdots vert & vert & vert & vert & vert & end{bmatrix}]

As we are able to see, the differentiation operator merely maps every foundation perform to its spinoff.

This outcome additionally applies to the bigger house of analytic actual features, which incorporates polynomials, exponential features, trigonometric features, logarithms, and different acquainted names.
By definition, an analytic perform may be expressed as a Taylor collection about (0):

[f[x] = sum_{n=0}^infty frac{f^{(n)}[0]}{n!}x^n = sum_{n=0}^infty alpha_n x^n]

Which is a linear mixture of our polynomial foundation features.
Which means a Taylor growth is basically a change of foundation into the sequence of powers, the place our differentiation operator is sort of easy.

---

Matrix decompositions are arguably the crowning achievement of linear algebra.
To get began, let’s evaluation what diagonalization means for a (3times3) actual matrix (mathbf{A}).

Eigenvectors

A vector (mathbf{u}) is an eigenvector of the matrix (mathbf{A}) when the next situation holds:

The eigenvalue (lambda) could also be computed by fixing the attribute polynomial of (mathbf{A}).
Eigenvalues could also be actual or complicated.

The matrix (mathbf{A}) is diagonalizable when it admits three linearly unbiased eigenvectors, every with a corresponding actual eigenvalue.
This set of eigenvectors constitutes an eigenbasis for the underlying vector house, indicating that we are able to categorical any vector (mathbf{x}) through their linear mixture.

To multiply (mathbf{x}) by (mathbf{A}), we simply should scale every element by its corresponding eigenvalue.

Lastly, re-combining the eigenvectors expresses the end in the usual foundation.

Intuitively, we’ve proven that multiplying by (mathbf{A}) is equal to a change of foundation, a scaling, and a change again.
Which means we are able to write (mathbf{A}) because the product of an invertible matrix (mathbf{U}) and a diagonal matrix (mathbf{Lambda}).

[begin{align*} mathbf{A} &= mathbf{ULambda U^{-1}}
&= begin{bmatrix}vert & vert & vert mathbf{u}_1 & mathbf{u}_2 & mathbf{u}_3 vert & vert & vert end{bmatrix}
begin{bmatrix}lambda_1 & 0 & 0 0 & lambda_2 & 0 0 & 0 & lambda_3 end{bmatrix}
begin{bmatrix}vert & vert & vert mathbf{u}_1 & mathbf{u}_2 & mathbf{u}_3 vert & vert & vert end{bmatrix}^{-1}
end{align*}] [begin{align*} mathbf{A} &= mathbf{ULambda U^{-1}}
&= begin{bmatrix}vert & vert & vert mathbf{u}_1 & mathbf{u}_2 & mathbf{u}_3 vert & vert & vert end{bmatrix}
& phantom{=} begin{bmatrix}lambda_1 & 0 & 0 0 & lambda_2 & 0 0 & 0 & lambda_3 end{bmatrix}
& phantom{=} begin{bmatrix}vert & vert & vert mathbf{u}_1 & mathbf{u}_2 & mathbf{u}_3 vert & vert & vert end{bmatrix}^{-1}
end{align*}]

Be aware that (mathbf{U}) is invertible as a result of its columns (the eigenvectors) kind a foundation for (mathbb{R}^3).
When multiplying by (mathbf{x}), (mathbf{U}^{-1}) converts (mathbf{x}) to the eigenbasis, (mathbf{Lambda}) scales by the corresponding eigenvalues, and (mathbf{U}) takes us again to the usual foundation.

Within the presence of complicated eigenvalues, (mathbf{A}) should be diagonalizable if we enable (mathbf{U}) and (mathbf{Lambda}) to incorporate complicated entires.
On this case, the decomposition as an entire nonetheless maps actual vectors to actual vectors, however the intermediate values turn into complicated.

Eigenfunctions

So, what does diagonalization imply in a vector house of features?
Given a linear operator (mathcal{L}), you may think a corresponding definition for eigenfunctions:

[mathcal{L}f = psi f]

The scalar (psi) is once more often called an eigenvalue.
Since (mathcal{L}) is infinite-dimensional, it doesn’t have a attribute polynomial—there’s not an easy technique for computing (psi).

Nonetheless, let’s try and diagonalize differentiation on analytic features.
Step one is to seek out the eigenfunctions.
Begin by making use of the above situation to our differentiation operator within the energy foundation:

[begin{align*}
&& frac{partial}{partial x}mathbf{p} = psi mathbf{p} vphantom&
&iff& begin{bmatrix}0 & 1 & 0 & 0 & cdots 0 & 0 & 2 & 0 & cdots 0 & 0 & 0 & 3 & cdots vdots & vdots & vdots & vdots & ddots end{bmatrix}begin{bmatrix}p_0 p_1 p_2 p_3 vdotsend{bmatrix}
&= begin{bmatrix}psi p_0 psi p_1 psi p_2 psi p_3 vdots end{bmatrix}
&iff& begin{cases} p_1 &= psi p_0 p_2 &= frac{psi}{2} p_1 p_3 &= frac{psi}{3} p_2 &dots end{cases} &
end{align*}]

This technique of equations implies that every one coefficients are decided solely by our selection of constants (p_0) and (psi).
We will explicitly write down their relationship as (p_i = frac{psi^i}{i!}p_0).

Now, let’s see what this class of polynomials truly seems like.

[p[x] = p_0 + p_0psi x + p_0frac{psi^2}{2}x^2 + p_0frac{psi^3}{6}x^3 + p_0frac{psi^4}{24}x^4 + dots] [begin{align*}
p[x] &= p_0 + p_0psi x + p_0frac{psi^2}{2}x^2, + &phantom{=} p_0frac{psi^3}{6}x^3 + p_0frac{psi^4}{24}x^4 + dots
finish{align*}]

Differentiation reveals that this perform is, in actual fact, an eigenfunction for the eigenvalue (psi).

[begin{align*} frac{partial}{partial x} p[x] &= 0 + p_0psi + p_0 psi^2 x + p_0frac{psi^3}{2}x^2 + p_0frac{psi^4}{6}x^3 + dots
&= psi p[x] finish{align*}] [begin{align*}
frac{partial}{partial x} p[x] &= 0 + p_0psi + p_0 psi^2 x, + &phantom{=} p_0frac{psi^3}{2}x^2 + p_0frac{psi^4}{6}x^3 + dots
&= psi p[x] finish{align*}]

With a little bit of algebraic manipulation, the definition of (e^{x}) pops out:

[begin{align*} p[x] &= p_0 + p_0psi x + p_0frac{psi^2}{2}x^2 + p_0frac{psi^3}{6}x^3 + p_0frac{psi^4}{24}x^4 + dots
&= p_0left((psi x) + frac{1}{2!}(psi x)^2 + frac{1}{3!}(psi x)^3 + frac{1}{4!}(psi x)^4 + dotsright)
&= p_0 e^{psi x} finish{align*}] [begin{align*}
p[x] &= p_0 + p_0psi x + p_0frac{psi^2}{2}x^2, + &phantom{=} p_0frac{psi^3}{6}x^3 + p_0frac{psi^4}{24}x^4 + dots
&= p_0Big((psi x) + frac{1}{2!}(psi x)^2, + &phantom{=p_0Big((} frac{1}{3!}(psi x)^3 + frac{1}{4!}(psi x)^4 + dotsBig)
&= p_0 e^{psi x}
finish{align*}]

Subsequently, features of the shape (p_0e^{psi x}) are eigenfunctions for the eigenvalue (psi), together with when (psi=0).

Diagonalizing Differentiation

We’ve discovered the eigenfunctions of the spinoff operator, however can we diagonalize it?
Ideally, we’d categorical differentiation as the mix of an invertible operator (mathcal{L}) and a diagonal operator (mathcal{D}).

[begin{align*} frac{partial}{partial x} &= mathcal{L} mathcal{D} mathcal{L}^{-1}
&=
begin{bmatrix} vert & vert & & alpha e^{psi_1 x} & beta e^{psi_2 x} & dots vert & vert & end{bmatrix}
begin{bmatrix} psi_1 & 0 & dots 0 & psi_2 & dots vdots & vdots & ddots end{bmatrix}
{color{red} begin{bmatrix} vert & vert & & alpha e^{psi_1 x} & beta e^{psi_2 x} & dots vert & vert & end{bmatrix}^{-1} }
end{align*}] [begin{align*} frac{partial}{partial x} &= mathcal{L} mathcal{D} mathcal{L}^{-1}
&=
begin{bmatrix} vert & vert & & alpha e^{psi_1 x} & beta e^{psi_2 x} & dots vert & vert & end{bmatrix}
& phantom{=} begin{bmatrix} psi_1 & 0 & dots 0 & psi_2 & dots vdots & vdots & ddots end{bmatrix}
& phantom{=} {color{red} begin{bmatrix} vert & vert & & alpha e^{psi_1 x} & beta e^{psi_2 x} & dots vert & vert & end{bmatrix}^{-1} }
end{align*}]

Diagonalization is barely potential when our eigenfunctions kind a foundation.
This is able to be true if all analytic features are expressible as a linear mixture of exponentials.
Nevertheless…

Actual exponentials don’t represent a foundation, so we can’t assemble an invertible (mathcal{L}).

The Laplace Remodel

We beforehand talked about that extra matrices may be diagonalized if we enable the decomposition to include complicated numbers.
Analogously, extra linear operators are diagonalizable within the bigger vector house of features from (mathbb{R}) to (mathbb{C}).

Differentiation works the identical method on this house; we’ll nonetheless discover that its eigenfunctions are exponential.

[frac{partial}{partial x} e^{(a+bi)x} = (a+bi)e^{(a+bi)x}]

Nevertheless, the brand new eigenfunctions have complicated eigenvalues, so we nonetheless can’t diagonalize.
We’ll want to contemplate the nonetheless bigger house of features from (mathbb{C}) to (mathbb{C}).

[frac{partial}{partial x} : (mathbb{C}mapstomathbb{C}) mapsto (mathbb{C}mapstomathbb{C})]

On this house, differentiation may be diagonalized through the Laplace transform.
Though helpful for fixing differential equations, the Laplace rework is non-trivial to invert, so we gained’t focus on it additional.
Within the following sections, we’ll delve into an operator that may be simply diagonalized in (mathbb{R}mapstomathbb{C}): the Laplacian.

---

Earlier than we get to the spectral theorem, we’ll want to grasp yet one more matter: internal merchandise.
You’re seemingly already acquainted with one instance of an internal product—the Euclidean dot product.

[begin{bmatrix}x y zend{bmatrix} cdot begin{bmatrix}a b cend{bmatrix} = ax + by + cz]

An internal product describes methods to measure a vector alongside one other vector.
For instance, (mathbf{u}cdotmathbf{v}) is proportional to the size of the projection of (mathbf{u}) onto (mathbf{v}).

With a little bit of trigonometry, we are able to present that the dot product is equal to multiplying the vectors’ lengths with the cosine of their angle.
This relationship means that the product of a vector with itself produces the sq. of its size.

[begin{align*} mathbf{u}cdotmathbf{u} &= |mathbf{u}||mathbf{u}|cos[0] &= |mathbf{u}|^2
finish{align*}]

Equally, when two vectors kind a proper angle (are orthogonal), their dot product is zero.

After all, the Euclidean dot product is just one instance of an internal product.
In additional basic areas, the internal product is denoted utilizing angle brackets, comparable to (langle mathbf{u}, mathbf{v} rangle).

• The size (also called the norm) of a vector is outlined as (|mathbf{u}| = sqrt{langle mathbf{u}, mathbf{u} rangle}).
• Two vectors are orthogonal if their internal product is zero: ( mathbf{u} perp mathbf{v} iff langle mathbf{u}, mathbf{v} rangle = 0).

A vector house augmented with an internal product is called an internal product house.

A Purposeful Internal Product

We will’t straight apply the Euclidean dot product to our house of actual features, however its (N)-dimensional generalization is suggestive.

[begin{align*} mathbf{u} cdot mathbf{v} &= u_1v_1 + u_2v_2 + dots + u_Nv_N &= sum_{i=1}^N u_iv_i end{align*}]

Given countable indices, we merely match up the values, multiply them, and add the outcomes.
When indices are uncountable, we are able to convert the discrete sum to its steady analog: an integral!

[langle f, g rangle = int_a^b f[x]g[x] , dx]

When (f) and (g) are comparable, multiplying them produces a bigger perform; once they’re completely different, they cancel out.
Integration measures their product over some area to supply a scalar outcome.

After all, not all features may be built-in.
Our internal product house will solely include features which might be square integrable over the area ([a, b]), which can be ([-infty, infty]).
Fortunately, the essential properties of our internal product don’t rely upon the selection of integration area.

Proofs

Under, we’ll briefly cowl features from (mathbb{R}) to (mathbb{C}).
On this house, our intuitive notion of similarity nonetheless applies, however we’ll use a barely extra basic internal product:

[langle f,g rangle = int_a^b f[x]overline{g[x]}, dx]

The place (overline{x}) denotes conjugation, i.e. (overline{a + bi} = a – bi).

Like different vector house operations, an internal product should fulfill a number of axioms:

Together with the definition (|f| = sqrt{langle f, f rangle}), these properties entail quite a lot of essential outcomes, together with the Cauchy–Schwarz and triangle inequalities.

---

Diagonalization is already a robust approach, however we’re constructing as much as an much more essential outcome concerning orthonormal eigenbases.
In an internal product house, an orthonormal foundation should fulfill two situations: every vector is unit size, and all vectors are mutually orthogonal.

A matrix consisting of orthonormal columns is called an orthogonal matrix.
Orthogonal matrices symbolize rotations of the usual foundation.

In an internal product house, matrix-vector multiplication computes the internal product of the vector with every row of the matrix.
One thing fascinating occurs after we multiply an orthogonal matrix (mathbf{U}) by its transpose:

[begin{align*}
mathbf{U}^Tmathbf{U} &=
begin{bmatrix}text{—} & mathbf{u}_1 & text{—} text{—} & mathbf{u}_2 & text{—} text{—} & mathbf{u}_3 & text{—} end{bmatrix}
begin{bmatrix}vert & vert & vert mathbf{u}_1 & mathbf{u}_2 & mathbf{u}_3 vert & vert & vert end{bmatrix}
&= begin{bmatrix} langle mathbf{u}_1, mathbf{u}_1 rangle & langle mathbf{u}_1, mathbf{u}_2 rangle & langle mathbf{u}_1, mathbf{u}_3 rangle
langle mathbf{u}_2, mathbf{u}_1 rangle & langle mathbf{u}_2, mathbf{u}_2 rangle & langle mathbf{u}_2, mathbf{u}_3 rangle
langle mathbf{u}_3, mathbf{u}_1 rangle & langle mathbf{u}_3, mathbf{u}_2 rangle & langle mathbf{u}_3, mathbf{u}_3 rangle end{bmatrix}
&= begin{bmatrix} 1 & 0 & 0 0 & 1 & 0 0 & 0 & 1 end{bmatrix}
&= mathcal{I}
end{align*}]

Since (mathbf{U}^Tmathbf{U} = mathcal{I}) (and (mathbf{U}mathbf{U}^T = mathcal{I})), we’ve discovered that the transpose of (mathbf{U}) is the same as its inverse.

When diagonalizing (mathbf{A}), we used (mathbf{U}) to rework vectors from our eigenbasis to the usual foundation.
Conversely, its inverse remodeled vectors from the commonplace foundation to our eigenbasis.
If (mathbf{U}) occurs to be orthogonal, reworking a vector (mathbf{x}) into the eigenbasis is equal to projecting (mathbf{x}) onto every eigenvector.

Moreover, the diagonalization of (mathbf{A}) turns into fairly easy:

[begin{align*} mathbf{A} &= mathbf{ULambda U^T}
&= begin{bmatrix}vert & vert & vert mathbf{u}_1 & mathbf{u}_2 & mathbf{u}_3 vert & vert & vert end{bmatrix}
begin{bmatrix}lambda_1 & 0 & 0 0 & lambda_2 & 0 0 & 0 & lambda_3 end{bmatrix}
begin{bmatrix}text{—} & mathbf{u}_1 & text{—} text{—} & mathbf{u}_2 & text{—} text{—} & mathbf{u}_3 & text{—} end{bmatrix} end{align*}] [begin{align*} mathbf{A} &= mathbf{ULambda U^T}
&= begin{bmatrix}vert & vert & vert mathbf{u}_1 & mathbf{u}_2 & mathbf{u}_3 vert & vert & vert end{bmatrix}
&phantom{=} begin{bmatrix}lambda_1 & 0 & 0 0 & lambda_2 & 0 0 & 0 & lambda_3 end{bmatrix}
&phantom{=} begin{bmatrix}text{—} & mathbf{u}_1 & text{—} text{—} & mathbf{u}_2 & text{—} text{—} & mathbf{u}_3 & text{—} end{bmatrix} end{align*}]

Given an orthogonal diagonalization of (mathbf{A}), we are able to deduce that (mathbf{A}) have to be symmetric, i.e. (mathbf{A} = mathbf{A}^T).

[begin{align*} mathbf{A}^T &= (mathbf{ULambda U}^T)^T
&= {mathbf{U}^T}^T mathbf{Lambda }^T mathbf{U}^T
&= mathbf{ULambda U}^T
&= mathbf{A}
end{align*}]

The spectral theorem states that the converse can be true: (mathbf{A}) is symmetric if and provided that it admits an orthonormal eigenbasis with actual eigenvalues.
Proving this result’s somewhat involved in finite dimensions and very involved in infinite dimensions, so we gained’t reproduce the proofs right here.

Self-Adjoint Operators

We will generalize the spectral theorem to our house of features, the place it states {that a} self-adjoint operator admits an orthonormal eigenbasis with actual eigenvalues.

Denoted as (mathbf{A}^{hspace{-0.1em}starhspace{0.1em}}), the adjoint of an operator (mathbf{A}) is outlined by the next relationship.

[langle mathbf{Ax}, mathbf{y} rangle = langle mathbf{x}, mathbf{A}^{hspace{-0.1em}starhspace{0.1em}}mathbf{y} rangle]

When (mathbf{A} = mathbf{A}^star), we are saying that (mathbf{A}) is self-adjoint.

The adjoint may be considered a generalized transpose—however it’s not apparent what which means in infinite dimensions.
We are going to merely use our practical internal product to find out whether or not an operator is self-adjoint.

The Laplace Operator

Earlier, we weren’t capable of diagonalize (actual) differentiation, so it should not be self-adjoint.
Subsequently, we are going to discover one other elementary operator, the Laplacian.

There are many equivalent definitions of the Laplacian, however in our house of one-dimensional features, it’s simply the second spinoff. We are going to therefore limit our area to twice-differentiable features.

[Delta f = frac{partial^2 f}{partial x^2}]

We could compute (Delta^star) utilizing two integrations by elements:

[begin{align*}
leftlangle Delta f[x], g[x] rightrangle &= int_a^b f^{primeprime}[x] g[x], dx
&= f^prime[x]g[x]Massive|_a^b – int_a^b f^{prime}[x] g^{prime}[x], dx
&= (f^prime[x]g[x] – f[x]g^{prime}[x])Massive|_a^b + int_a^b f[x] g^{primeprime}[x], dx
&= leftlangle f[x], Delta g[x] rightrangle
finish{align*}] [begin{align*}
leftlangle Delta f[x], g[x] rightrangle &= int_a^b f^{primeprime}[x] g[x], dx
&= f^prime[x]g[x]Massive|_a^b – int_a^b f^{prime}[x] g^{prime}[x], dx
&= (f^prime[x]g[x] – f[x]g^{prime}[x])Massive|_a^b &hphantom{=}+ int_a^b f[x] g^{primeprime}[x], dx
&= leftlangle f[x], Delta g[x] rightrangle
finish{align*}]

Within the last step, we assume that ((f^prime[x]g[x] – f[x]g^{prime}[x])massive|_a^b = 0), which isn’t true generally.
To make our conclusion legitimate, we are going to constrain our area to solely embrace features satisfying this boundary situation.
Particularly, we are going to solely contemplate periodic features with interval (b-a).
These features have the identical worth and spinoff at (a) and (b), so the extra time period vanishes.

For simplicity, we may even assume our area to be ([0,1]).
For instance:

Subsequently, the Laplacian is self-adjoint…virtually.
Technically, we’ve proven that the Laplacian is symmetric, not that (Delta = Delta^star).
It is a refined level, and it’s potential to show self-adjointness, so we are going to omit this element.

Laplacian Eigenfunctions

Making use of the spectral theorem tells us that the Laplacian admits an orthonormal eigenbasis.
Let’s discover it.

Because the Laplacian is solely the second spinoff, actual exponentials would nonetheless be eigenfunctions—however they’re not periodic, so we’ll should exclude them.

[color{red} Delta e^{psi x} = psi^2 e^{psi x}]

Fortunately, a brand new class of periodic eigenfunctions seems:

[begin{align*} Delta sin[psi x] &= -psi^2 sin[psi x] Delta cos[psi x] &= -psi^2 cos[psi x] finish{align*}]

If we enable our diagonalization to introduce complicated numbers, we are able to additionally contemplate features from (mathbb{R}) to (mathbb{C}) .
Right here, purely complicated exponentials are eigenfunctions with actual eigenvalues.

[begin{align*} Delta e^{psi i x} &= (psi i)^2e^{psi i x}
&= -psi^2 e^{psi i x}
&= -psi^2 (cos[psi x] + isin[psi x]) tag{Euler’s components} finish{align*}] [begin{align*} Delta e^{psi i x} &= (psi i)^2e^{psi i x}
&= -psi^2 e^{psi i x}
&= -psi^2 (cos[psi x] + isin[psi x]) & tag{Euler’s components} finish{align*}]

Utilizing Euler’s components, we are able to see that these two views are equal: they each introduce (sin) and (cos) as eigenfunctions.
Both path can result in our last outcome, however we’ll persist with the extra compact complicated case.

We additionally must constrain the set of eigenfunctions to be periodic on ([0,1]).
As instructed above, we are able to pick the eigenvalues which might be an integer a number of of (2pi).

[e^{2pi xi i x} = cos[2pi xi x] + isin[2pi xi x]]

Our set of eigenfunctions is subsequently (e^{2pi xi i x}) for all integers (xi).

Diagonalizing the Laplacian

Now that we’ve discovered appropriate eigenfunctions, we are able to assemble an orthonormal foundation.

Our assortment of eigenfunctions is linearly unbiased, as every one corresponds to a definite eigenvalue.
Subsequent, we are able to examine for orthogonality and unit magnitude:

The ultimate step is to indicate that every one features in our area may be represented by a linear mixture of eigenfunctions.
To take action, we are going to discover an invertible operator (mathcal{L}) representing the correct change of foundation.

Critically, since our eigenbasis is orthonormal, we are able to intuitively contemplate the inverse of (mathcal{L}) to be its transpose.

[mathcal{I} = mathcal{L}mathcal{L}^{-1} = mathcal{L}mathcal{L}^{T} = begin{bmatrix} vert & vert & & e^{2pixi_1 i x} & e^{2pixi_2 i x} & dots vert & vert & end{bmatrix}begin{bmatrix} text{—} & e^{2pixi_1 i x} & text{—} text{—} & e^{2pixi_2 i x} & text{—} & vdots & end{bmatrix}] [begin{align*} mathcal{I} &= mathcal{L}mathcal{L}^{-1} &= mathcal{L}mathcal{L}^{T} &= begin{bmatrix} vert & vert & & e^{2pixi_1 i x} & e^{2pixi_2 i x} & dots vert & vert & end{bmatrix} & phantom{=} begin{bmatrix} text{—} & e^{2pixi_1 i x} & text{—} text{—} & e^{2pixi_2 i x} & text{—} & vdots & end{bmatrix} end{align*}]

This visualization means that (mathcal{L}^Tf) computes the internal product of (f) with every eigenvector.

[mathcal{L}^Tf = begin{bmatrix}langle f, e^{2pixi_1 i x} rangle langle f, e^{2pixi_2 i x} rangle vdots end{bmatrix}]

Which is very harking back to the finite-dimensional case, the place we projected onto every eigenvector of an orthogonal eigenbasis.

This perception permits us to write down down the product (mathcal{L}^Tf) as an integer perform (hat{f}[xi]).
Be aware that the complicated internal product conjugates the second argument, so the exponent is negated.

[(mathcal{L}^Tf)[xi] = hat{f}[xi] = int_0^1 f[x]e^{-2pixi i x}, dx]

Conversely, (mathcal{L}) converts (hat{f}) again to the usual foundation.
It merely creates a linear mixture of eigenfunctions.

[(mathcal{L}hat{f})[x] = f[x] = sum_{xi=-infty}^infty hat{f}[xi] e^{2pixi i x}]

These operators are, in actual fact, inverses of one another, however a rigorous proof is past the scope of this publish.
Subsequently, we’ve diagonalized the Laplacian:

[begin{align*} Delta &= mathcal{L} mathcal{D} mathcal{L}^T
&=
begin{bmatrix} vert & vert & & e^{2pixi_1 i x} & e^{2pixi_2 i x} & dots vert & vert & end{bmatrix}
begin{bmatrix} -(2pixi_1)^2 & 0 & dots 0 & -(2pixi_2)^2 & dots vdots & vdots & ddots end{bmatrix}
begin{bmatrix} text{—} & e^{2pixi_1 i x} & text{—} text{—} & e^{2pixi_2 i x} & text{—} & vdots & end{bmatrix}
end{align*}] [begin{align*} Delta &= mathcal{L} mathcal{D} mathcal{L}^T
&=
begin{bmatrix} vert & vert & & e^{2pixi_1 i x} & e^{2pixi_2 i x} & dots vert & vert & end{bmatrix}
& phantom{=} begin{bmatrix} -(2pixi_1)^2 & 0 & dots 0 & -(2pixi_2)^2 & dots vdots & vdots & ddots end{bmatrix}
& phantom{=} begin{bmatrix} text{—} & e^{2pixi_1 i x} & text{—} text{—} & e^{2pixi_2 i x} & text{—} & vdots & end{bmatrix}
end{align*}]

Though (mathcal{L}^T) transforms our real-valued perform right into a complex-valued perform, (Delta) as an entire nonetheless maps actual features to actual features.
Subsequent, we’ll see how (mathcal{L}^T) is itself an extremely helpful transformation.

---

On this part, we’ll discover a number of purposes in signal processing, every of which arises from diagonalizing the Laplacian on a brand new area.

When you’re acquainted with Fourier strategies, you seemingly observed that (hat{f}) encodes the Fourier collection of (f).
That’s as a result of a Fourier rework is a change of foundation into the Laplacian eigenbasis!

This foundation consists of waves, which makes (hat{f}) is a very fascinating illustration for (f).
For instance, contemplate evaluating (hat{f}[1]):

[hat{f}[1] = int_0^1 f[x] e^{-2pi i x}, dx = int_0^1 f[x](cos[2pi x] – isin[2pi x]), dx] [begin{align*} hat{f}[1] &= int_0^1 f[x] e^{-2pi i x}, dx &= int_0^1 f[x](cos[2pi x] – isin[2pi x]), dx finish{align*}]

This integral measures how a lot of (f) is represented by waves of frequency (constructive) 1.
Naturally, (hat{f}[xi]) computes the same amount for any integer frequency (xi).

[hphantom{aaa} {color{#9673A6} text{Real}left[e^{2pi i xi x}right]},,,,,,,, {coloration{#D79B00} textual content{Complicated}left[e^{2pi i xi x}right]}]

Subsequently, we are saying that (hat{f}) expresses our perform within the frequency area.
As an example this level, we’ll use a Fourier collection to decompose a piecewise linear perform into a group of waves.
^{Since our new foundation is orthonormal, the rework is straightforward to invert by re-combining the waves.}

Right here, the (coloration{#9673A6}textual content{purple}) curve is (f); the (coloration{#D79B00}textual content{orange}) curve is a reconstruction of (f) from the primary (N) coefficients of (hat{f}).
Attempt various the variety of coefficients and shifting the (coloration{#9673A6}textual content{purple}) dots to impact the outcomes.

Many fascinating operations turn into simple to compute within the frequency area.
For instance, by merely dropping Fourier coefficients past a sure threshold, we are able to reconstruct a smoothed model of our perform.
This system is called a low-pass filter—strive it out above.

Computationally, Fourier collection are particularly helpful for compression.
Encoding a perform (f) in the usual foundation takes plenty of house, since we retailer a separate outcome for every enter.
If we as a substitute categorical (f) within the Fourier foundation, we solely must retailer a couple of coefficients—we’ll be capable to roughly reconstruct (f) by re-combining the corresponding foundation features.

To this point, we’ve solely outlined a Fourier rework for features on (mathbb{R}).
Fortunately, the rework arose through diagonalizing the Laplacian, and the Laplacian will not be restricted to one-dimensional features.
In truth, wherever we are able to outline a Laplacian, we are able to discover a corresponding Fourier rework.

For instance, in two dimensions, the Laplacian turns into a sum of second derivatives.

[Delta f[x,y] = frac{partial^2 f}{partial x^2} + frac{partial^2 f}{partial y^2}]

For the area ([0,1]occasions[0,1]), we’ll discover a acquainted set of periodic eigenfunctions.

[e^{2pi i(nx + my)} = cos[2pi(nx + my)] + isin[2pi(nx + my)]] [begin{align*} e^{2pi i(nx + my)} &= cos[2pi(nx + my)], + &phantom{=}, isin[2pi(nx + my)] finish{align*}]

The place (n) and (m) are each integers.
Let’s see what these foundation features appear like:

Identical to the 1D case, the corresponding Fourier rework is a change of foundation into the Laplacian’s orthonormal eigenbasis.
Above, we decomposed a 1D perform into a group of 1D waves—right here, we equivalently decompose a 2D picture into a group of 2D waves.

A variant of the 2D Fourier rework is on the core of many picture compression algorithms, together with JPEG.

Spherical Harmonics

Laptop graphics is usually involved with features on the unit sphere, so let’s see if we are able to discover a corresponding Fourier rework.
In spherical coordinates, the Laplacian may be outlined as follows:

[Delta f(theta, phi) = frac{1}{sin[theta]}frac{partial}{partial theta}left(sin[theta] frac{partial f}{partial theta}proper) + frac{1}{sin^2[theta]}frac{partial^2 f}{partial phi^2}] [begin{align*}
Delta f(theta, phi) &= frac{1}{sin[theta]}frac{partial}{partial theta}left(sin[theta] frac{partial f}{partial theta}proper), + &phantom{=} frac{1}{sin^2[theta]}frac{partial^2 f}{partial phi^2}
finish{align*}]

We gained’t undergo the complete derivation, however this Laplacian admits an orthornormal eigenbasis often called the spherical harmonics.

[Y_ell^m[theta, phi] = N_ell^m P_ell^m[cos[theta]] e^{imphi}]

The place (Y_ell^m) is the spherical harmonic of diploma (ell ge 0) and order (m in [-ell,ell]). Be aware that (N_ell^m) is a continuing and (P_ell^m) are the associated Legendre polynomials.

[hphantom{aa} {color{#9673A6} text{Real}left[Y_ell^m[theta,phi]proper]},,,,,,,, {coloration{#D79B00} textual content{Complicated}left[Y_ell^m[theta,phi]proper]}]

As above, we outline the spherical Fourier rework as a change of foundation into the spherical harmonics.
In recreation engines, this rework is usually used to compress diffuse surroundings maps (i.e. spherical photographs) and world illumination probes.

You may also acknowledge spherical harmonics as electron orbitals—quantum mechanics is primarily involved with the eigenfunctions of linear operators.

Representing features as vectors underlies many fashionable algorithms—picture compression is just one instance.
In truth, as a result of computer systems can do linear algebra so effectively, making use of linear-algebraic methods to features produces a robust new computational paradigm.

The nascent discipline of discrete differential geometry makes use of this angle to construct algorithms for three-dimensional geometry processing.
In laptop graphics, features on meshes typically symbolize textures, unwrappings, displacements, or simulation parameters.
DDG offers us a approach to faithfully encode such features as vectors: for instance, by associating a worth with every vertex of the mesh.

One notably related result’s a Laplace operator for meshes.
A mesh Laplacian is a finite-dimensional matrix, so we are able to use numerical linear algebra to seek out its eigenfunctions.

As with the continual case, these features generalize sine and cosine to a brand new area.
Right here, we visualize the actual and sophisticated elements of every eigenfunction, the place the 2 colours point out constructive vs. unfavorable areas.

[hphantom{aa} {color{#9673A6} text{Rea}}{color{#82B366}text{l}left[psi_Nright]},,,,,,,, {coloration{#D79B00} textual content{Comp}}{coloration{#6C8EBF} textual content{lex}left[psi_Nright]}]

At this level, the implications is perhaps apparent—this eigenbasis is beneficial for reworking and compressing features on the mesh.
In truth, by decoding the vertices’ positions as a perform, we are able to even clean or sharpen the geometry itself.

There’s much more to sign and geometry processing than we are able to cowl right here, not to mention the various different purposes in engineering, physics, and laptop science.
We are going to conclude with an (incomplete, biased) record of matters for additional exploration. See for those who can observe the functions-are-vectors thread all through:

• Geometry: Distances, Parallel Transport, Flattening, Non-manifold Meshes, and Polygonal Meshes
• Simulation: the Finite Element Method, Monte Carlo PDEs, Minimal Surfaces, and Fluid Cohomology
• Gentle Transport: Radiosity, Operator Formulation (Ch.4), Low-Rank Approximation, and Inverse Rendering
• Machine Studying: DiffusionNet, MeshCNN, Kinematics, Fourier Features, and Inverse Geometry
• Splines: C2 Interpolation, Quadratic Approximation, and Simplification

Because of Joanna Y, Hesper Yin, and Fan Pu Zeng for offering suggestions on this publish.

---