"Maymester MATH547 Linear Algebra for Applications in Data Science"

Data Efficiency

1.Krylov bases

In reduction of the model

𝑨 𝒙 = 𝒚, 𝑨 \in ℝ^{m \times n}, ℝ^{n} \overset{𝑨}{\to} ℝ^{m}

by restriction to a subspaces spanned by the orthogonal column vectors of $𝑩, 𝑪$ , $𝒙 = 𝑩 𝒖$ , $𝒚 = 𝑪 𝒗$ , the reduced model

𝒗 = 𝑹 𝒖

is obtained with $𝑹 = 𝑪^{T} 𝑨 𝑩$ , the reduced system matrix. The choice of the basis sets $𝑩, 𝑪$ is not yet specified. One common choice is to use the singular value decomposition $𝑨 = 𝑺 𝚺 𝑸^{T}$ and choose the dominant $k$ singular vectors to span the subspaces,

𝑩 = 𝑸_{k}, 𝑪 = 𝑺_{k} .

This assumes that an SVD is available, and that ordering of vectors by the $2$ -norm is relevant to the problem. This is often the case in problems in which the matrix $𝑨$ somewhow expresses the energy of a system. For example in deformation of a structure a relationship between forces $𝒇$ and displacements $𝒖$ is approximated linearly by $𝒇 = 𝑲 𝒖$ , with the stiffness matrix $𝑲$ expressing the potential energy stored in the deformation.

However in many cases, the model might not express an energy so the 2-norm is not an appropriate functional, or even if it is the size of the problem might render the computation of the singular value decomposition impractical. In such situations alternative procedures to construct reduced bases must be devised.

Consider that the only information available about the problem are the matrix $𝑨 \in ℝ^{m \times m}$ and a vector $𝒚 \in ℝ^{m}$ . From these two a sequence of vectors can be gather into what is known as a Krylov matrix

𝑲_{n} = [\begin{array}{ccccc} 𝒚 & 𝑨 𝒚 & 𝑨^{2} 𝒚 & \dots & 𝑨^{n - 1} 𝒚 \end{array}] .

The Krylov matrix $𝑲_{n}$ is generally not orthogonal, but an orthogonal basis can readily be extracted through the $Q R$ factorization

𝑸_{n} 𝑹 = 𝑲_{n} .

The basis $𝑸_{n}$ can then be adopted, both for the domain and the codomain

𝑩 = 𝑪 = 𝑸_{n} .

2.Greedy approximation

The Krylov procedure has the virtue of simplicity, but does not have the desirable property of the SVD of ordering of the singular vectors. Suppose that the system matrix $𝑨 \in ℝ^{m \times m}$ is applied to $k$ vectors $𝒙_{1}, \dots, 𝒙_{k}$ , leading to formation of the vector set $S = {𝑨 𝒙_{1}, \dots, 𝑨 𝒙_{k}}$ . Denote by $𝑩$ the first $n$ members of the set ordered in some arbitrary norm

𝑩 = [\begin{array}{cccc} 𝒃_{1} & 𝒃_{2} & \dots & 𝒃_{n} \end{array}], n ≪ k

𝒃_{1} = 𝑨 𝒙_{σ (1)}, \dots,_{} 𝒃_{k} = 𝑨 𝒙_{σ (k)},

where $σ$ denotes the permutation that orders the vectors in accordance with the chosen norm. The above is called a greedy approximation, and furnishes an alternative to the SVD that exhibits an ordering property. As in the Krylov case, it is usually more efficient to use an orthogonal set obtained through $Q R$ factorization

𝑸_{n} 𝑹 = 𝑩_{n} .