[DSP] W02 - Vector Spaces

contents

• discrete signal vectors
  • vector space framework
• vector spaces
  • vector space axioms
  • inner product
  • norm and distance
• signal spaces
  • completeness
  • common signal spaces
• bases
  • vector families
  • orthonormal basis
  • change of basis
• subspaces
  • vector subspace
  • least square approximations
  • approximation with Legendre polynomials
  • haar spaces
• references

---

discrete signal vectors

• a generic discrete signal:
  • $x\left[n\right]=\dots ,1.23,-0.73,0.89,0.17,-1.15,-0.26,\dots$
  • set of ordered number sequence
• four classes of signals
  • finite length
  • infinite length
  • periodic
  • finite support
• digital signal processing:
  • signal analysis
  • signal synthesis
• number sets:
  • $N$: natural numbers $[1,\infty )$
    • whole numbers $[0,\infty )$
  • $Z$: integers
  • $Q$: rational numbers
    • inclusive of recurring mantissa
  • $P$: irrational numbers
    • non-repeating and non-recurring mantissa
    • $\pi$ value, $\sqrt{2}$
  • $R$: real numbers (everything on the number line)
    • includes rational and irrational numbers
  • $C$: complex numbers
    • includes real and imaginary numbers

fig: number sets

---

vector space framework:

• justification for dsp application:
  • common framework for various signal classes
    • inclusive of continuous-time signals
  • easy explanation of Fourier Transform
  • easy explanation of sampling and interpolation
  • useful in approximation and compression
  • fundamental to communication system design
• paradigms for vector space application to discrete signals
  • object oriented programming
    • the instantiated object can have unique property values
    • but for a given object class, the properties and methods are the same
  • lego
    • various unit blocks, same and different
    • units assembled in different ways to build different complex structures
    • similarly, a complex signal is broken down into a combination of basis vectors for analysis
• key takeaways
  • vector spaces are general objects
  • vector spaces are defined by their properties
  • once signal properties satisfy vector space conditions
    • vector space tools can be applied to signals

---

vector spaces

• some vector spaces
  • $R^2$: 2D space
  • $R^3$: 3D space
  • $R^N$: N real numbers
  • $C^N$: N complex numbers
  • ${\ell }_2\left(Z\right)$:
    • square-summable infinite sequences
  • $L_2\left(\right[a,b\left]\right)$:
    • square-integrable functions over interval $[a,b]$
• vector spaces can be diverse
• some vector spaces can be represented graphically
  • helps visualize the signal for analysis insights
• $R^2$: $\text{x}=[x_0,x_1{]}^T$
• $R^3$: $\text{x}=[x_0,x_1,x_2{]}^T$
  • both can be visualized in a cartesian system fig: vector in 2D space
• $L_2\left(\right[a,b\left]\right)$: $\text{x}=x\left(t\right),t\in [-1,1]$
  • function vector space
  • can be represented as sine wave along time fig: L2 function vector
• others cannot be represented graphically:
  • $R^N$ for $N>3$
  • $C^N$ for $N>1$

---

vector space axioms

• informally, a vector space:
  • has vectors in it
  • has scalars in it, like $C$
  • scalers must be able to scale vectors
  • vector summation must work
• formally, $\forall \text{x,y,z}\in V,and\alpha ,\beta \in C$ ($V$: vector space)
  • $\text{x}+\text{y}=\text{y}+\text{x}$
    • commutative addition
  • $(\text{x}+\text{y})+\text{z}=\text{x}+(\text{y}+\text{z})$
    • distributive addition
  • $\alpha (\text{x}+\text{y})=\alpha \text{y}+\alpha \text{x}$
    • distributive scalar multiplication over vectors
  • $(\alpha +\beta )\text{x}=\alpha \text{x}+\beta \text{x}$
    • distributive vector multiplication over scalers
  • $\alpha \left(\beta \text{x}\right)=\alpha \left(\beta \text{x}\right)$
    • associative scalar multiplication
  • $\exists 0\in V|\text{x}+0=0+\text{x}=\text{x}$
    • null vector, $0$, exists
    • addition of $0$ and another vector $\text{x}$ returns $\text{x}$
    • summation with null vector is commutative
  • $\forall \text{x}\in V\exists (-\text{x})|\text{x}+(-x)=0$
    • an inverse vector exists in vector space such that adding the vector with it’s inverse yields the null vector
• examples:
  • $R^N$: vector of N real numbers
    • two vectors from this space look like:
      • $\text{x}=[x_0,x_1,x_2,\dots x_N{]}^T$
      • $\text{y}=[x_0,x_1,x_2,\dots x_N{]}^T$
    • the above mentioned rules apply to these vectors and can be verified
  • $L_2[-1,1]$

---

inner product

• aka dot product: measure of similarity of two vectors
  • $⟨\cdot ,\cdot ⟩:V\times V\to C$
• takes two vectors and outputs a scaler which indicates how similar the two vectors are
• inner product axioms
  • $⟨x+y,z⟩=⟨x,z⟩+⟨y,z⟩$
    • distributive over vector addition
  • $⟨x,y⟩=⟨y,x{⟩}^{\ast }$
    • commutative with conjugation
  • $⟨x,\alpha y⟩=\alpha ⟨x,y⟩$
    • distributive with scalar multiplication
    • when scalar scales the second operand
  • $⟨\alpha x,y⟩={\alpha }^{\ast }⟨x,y⟩$
    • distributive with scalar multiplication
    • conjugate scalar if it scaling the first operand
  • $⟨x,x⟩\ge 0$
    • self inner product ( \in \mathbb{R})
  • $⟨x,x⟩=0\iff x=0$
    • if self inner product is 0, then the vector is the null vector
  • if $⟨x,y⟩=0andx,y\ne 0$,
    • then $x$ and $y$ are orthogonal
• inner product is computed differently for different vector spaces
• in $R^2$ vector space:
  • $⟨x,y⟩=x_0{y}_0+x_1{y}_1=\parallel x\parallel \parallel y\parallel \cos \alpha$
    • where $\alpha$: angle between $x$ and $y$
  • when two vectors are orthogonal to each other
    • $\alpha ={90}^{\circ }$, so $\cos {90}^{\circ }=0$, so $⟨x,y⟩=0$
• in $L_2[-1,1]$ vector space:
  • $⟨x,y⟩={\int }_{-1}^{1}x\left(t\right)y\left(t\right)dt$
    • norm: $⟨x,x⟩=\parallel x{\parallel }^2={\int }_{-1}^1{\sin }^2\left(\pi t\right)dt$
  • the inner product of a symmetric and an anti-symmetric function is 0
    • i.e. they are orthogonal to each other and cannot be expressed as a factor of the other in any way
    • example 1:
      • $x=\sin \left(\pi t\right)$ - anti-symmetric
      • $y=1-\left|t\right|$ - symmetric
      • $⟨x,y⟩={\int }_{-1}^1\left(\sin \right(\pi t\left)\right)(1-|t\left|\right)dt=0$

      

      fig: inner product of a symmetric and an anti-symmetric function

    • example 2:
      • $x=\sin \left(4\pi t\right)$
      • $y=\sin \left(5\pi t\right)$
      • $⟨x,y⟩={\int }_{-1}^1\left(\sin \right(4\pi t\left)\right)\left(\sin \right(5\pi t\left)\right)dt=0$

---

norm and distance

• norm of a vector: - inner product of a vector with itself - square of the norm (length) of a vector - $⟨x,x⟩=x_0^2+x_1^2=\parallel x{\parallel }^2$
• distance between two vectors:
  • the norm of the difference of the two vectors
• the distance between orthogonal vectors is not zero
• in $R^2$, norm is the distance between the vector end points
  • $\parallel x-y\parallel$ is the difference vector
  • $\parallel x-y\parallel =\sqrt{(x_0-y_0{)}^2+(x_1-y_1{)}^2}$
    • connects the end points of the vectors $x$ and $y$
  • see triangle rule of vector addition, and pythagorean theorem
• in $L_2[-1,1]$, the norm is the mean-squared error:
  • ${\int }_{-1}^1\left|x\right(t)-y(t){|}^{2}dt$

---

signal spaces

completeness

• consider an infinite sequence of vectors in a vector space
• if it converges to a limit within the vector space
  • then said vector space is “complete”
  • also called Hilbert Space
• limiting operation is ambiguous, definition varies from one space to the other
• so some limiting operation may fail and point outside the vector space
  • such vector spaces are not said to be complete

---

common signal spaces

• while vectors spaces can be applied to signal processing
  • not all vector spaces can be used for all signals
• different signal classes are managed in different spaces
• $C^N$: vector space of N complex tuples
  • valid signal space for finite length signals
    • vector notation: $\text{x}=[x_0,x_1,\dots x_N{]}^T$
    • where $x_0,x_1\dots x_N$ are complex tuples
  • also valid for periodic signals
    • vector notation: $\tilde{\text{x}}$
  • all operations are well defined and intuitive
  • inner product: $⟨\text{x,y}⟩={\sum }_{n=0}^{N-1}{x}^{\ast }\left[n\right]y\left[n\right]$
    • well defined for all finite-length vectors in ( \mathbb{C}^N)
• the inner product for infinite length signals explode in $C^N$ - inappropriate for infinite length signal analysis
• ${\ell }_2\left(Z\right)$: vector space of square-summable sequences - requirement for sequences to be square-summable: - $\sum \left|x\right[n]{|}^2<\infty$ - sum of squares of elements of the sequence is less than infinity - all sequences that live in this space must have finite energy - “well-behaved” infinite-length signals live in ${\ell }_2\left(Z\right)$ - vector notation: $\text{x}=[\dots ,x_{-2},x_{-1},x_0,x_1,\dots {]}^T$
• lot of other interesting infinite length signals do not live in ${\ell }_2$
  • examples:
    • $x\left[n\right]=1$
    • $x\left[n\right]=\cos \left(\omega n\right)$
  • these have to be dealt with case-by-case

---

basis

• a basis is a building block of a vector space
  • a vector space usually has a few basis vectors called bases
  • like the lego unit blocks
• any element in a vector space can be
  • built with a combination of these bases
  • decomposed into a linear combination of these bases
• the basis of a space is a family of vectors which are least like each other
  • but they all belong to the same space
  • as a linear combination, the basis vectors capture all the information within their vector space
• fourier transform is simply a change of basis

---

vector families

• ${\text{w}}^{\left(k\right)}$: family of vectors - $k$: index of the basis in the family
• canonical $R^2$ basis: ${\text{e}}^k$
  • ${\text{e}}^{\left(0\right)}=\left[\begin{array}{c}10\end{array}\right]\text{;}{\text{e}}^{\left(1\right)}=\left[\begin{array}{c}01\end{array}\right]$
  • this family of basis vectors is denoted by ${\text{e}}^k$
• any vector can be expressed as a linear combination of ( \textbf{e}^k) in ( \mathbb{R}^2 )
  • $\left[\begin{array}{c}{x}_0{x}_1\end{array}\right]=x_0\left[\begin{array}{c}10\end{array}\right]+x_1\left[\begin{array}{c}01\end{array}\right]$
  • $\text{x}=x_0{\text{e}}^{\left(0\right)}+x_1{\text{e}}^{\left(1\right)}$
• graphical example:
  • $\left[\begin{array}{c}21\end{array}\right]=2\left[\begin{array}{c}10\end{array}\right]+1\left[\begin{array}{c}01\end{array}\right]$
  • $\text{x}=2{\text{e}}^{\left(0\right)}+1{\text{e}}^{\left(1\right)}$

fig: linear combination of canonical ( \textbf{e}^k) in (\mathbb{R}^2)

• non-canonical $R^2$ basis example: ${\text{v}}^k$
  • ${\text{v}}^{\left(0\right)}=\left[\begin{array}{c}10\end{array}\right]\text{;}{\text{v}}^{\left(1\right)}=\left[\begin{array}{c}11\end{array}\right]$
• any vector can be expressed as a linear combination of these vectors in $R^2$
  • the coefficients of the bases will be different compared to the canonical bases
• graphical example:
  • $\left[\begin{array}{c}21\end{array}\right]=\alpha {\text{v}}^{\left(0\right)}+\beta {\text{v}}^{\left(1\right)}$
  • $\left[\begin{array}{c}21\end{array}\right]=\alpha \left[\begin{array}{c}10\end{array}\right]+\beta \left[\begin{array}{c}11\end{array}\right]$
    • by rule of parallelogram vector addition
  • $\alpha =1\text{;}\beta =1$

fig: linear combination of non-canonical ${\text{v}}^k$ in $R^2$

• only vectors which are linearly independent can be the basis vectors of a space
• infinite dimensional spaces bases:
  • some limitations have to be applied to obtain basis vectors of infinite dimension
  • $\text{x}={\sum }_{k=0}^{\infty }{\alpha }_k{\text{w}}^{\left(k\right)}$
• a canonical basis of ${\ell }_2\left(Z\right)$ - ${\text{e}}^k=\left[\begin{array}{c}.\\ .\\ .\\ 0\\ 0\\ 1\\ 0\\ 0\\ 0\\ .\\ .\\ .\end{array}\right]$, $k$ -th position, $k\in Z$
• function vector spaces:
  • basis vector for functions: $f\left(t\right)={\sum }_k{\alpha }_k{\text{h}}^{\left(k\right)}\left(t\right)$
• the fourier basis for functions over an interval $[-1,1]$: - $\frac{1}{\sqrt{2}},\cos \pi t,\sin \pi t,\cos 2\pi t,\sin 2\pi t,\cos 3\pi t,\sin 3\pi t,\dots$ - any square-integrable function in $[-1,1]$ can be represented as a linear combination of fourier bases - a square wave can be expressed as a sum of sines
• formally, in a vector space $H$,
• a set of $K$ vectors from $H$, $W={{\text{w}}^{\left(k\right)}}_{k=0,1,\dots ,K-1}$ is a basis for $H$ if: `
  1. $\forall \in H$: $\text{x}={\sum }_{k=0}^{K-1}{\alpha }_k{\text{w}}^{\left(k\right)}$, ${\alpha }_k\in C$
  2. the coefficients ${\alpha }_k$ are unique
     • this implies linear independence in the vector basis
     • ${\sum }_{k=0}^{K-1}{\alpha }_k{\text{w}}^{\left(k\right)}=0\iff {\alpha }_k=0,k=0,1,\dots ,K-1$ `

orthonormal basis

• the orthogonal bases are the most important
  • of all possible bases for a vector space
• orthogonal basis: $⟨{\text{w}}^{\left(k\right)},{\text{w}}^{\left(n\right)}⟩=0$ for $k\ne n$
  • vectors of an orthogonal basis are mutually orthogonal
  • their inner product with each other is zero
• in some spaces, the orthogonal bases are also orthonormal
  • i.e. they are unit norm
  • their length $\parallel {\text{w}}^{\left(k\right)}\parallel =1$
• the inner product of any two vectors in the orthonormal bases is the difference between their indices
  • $⟨{\text{w}}^{\left(k\right)},{\text{w}}^{\left(n\right)}⟩=\delta [n-k]$
• gran-schmidt algorithm can be used to orthonormalize any orthogonal bases
• obtaining the bases coefficients ${\alpha }_k$ for bases can be involved and challenging
  • $\text{x}={\sum }_{k=0}^{K-1}{\alpha }_k{\text{w}}^{\left(k\right)}$
    • $\text{x}$: a vector as the linear combination of $K$ basis vectors ${\text{w}}^{\left(k\right)}$,
    • with corresponding coefficients ${\alpha }_k$
  • however, they are easy to obtain with an orthonormal basis
    • ${\alpha }_k=⟨{\text{w}}^{\left(k\right)},\text{x}⟩$

---

change of basis

• $\text{x}={\sum }_{k=0}^{K-1}{\alpha }_k{\text{w}}^{\left(k\right)}={\sum }_{k=0}^{K-1}{\beta }_k{\text{v}}^{\left(k\right)}$
  • ${\text{v}}^{\left(k\right)}$ is the target basis, ${\text{w}}^{\left(k\right)}$ is the original basis
• if ${\text{v}}^{\left(k\right)}$ is orthonormal:
  • ${\beta }_h=⟨v^{\left(h\right)},\text{x}⟩$
  • $=⟨{\text{v}}^{\left(h\right)},{\sum }_{k=0}^{K-1}{\alpha }_k{\text{w}}^{\left(k\right)}⟩$
  • $={\sum }_{k=0}^{K-1}{\alpha }_k⟨{\text{v}}^{\left(h\right)},{\text{w}}^{\left(k\right)}⟩$
  • $={\sum }_{k=0}^{K-1}{\alpha }_k{c}_{hk}$
  • $=\left[\begin{array}{cccc}{c}_{00}& c_{01}& \dots & c_{0(K-1)}\\ & & ⋮& \\ c_{(K-1)0}& c_{(K-1)1}& \dots & c_{(K-1)(K-1)}\end{array}\right]\left[\begin{array}{c}{\alpha }_0⋮\\ {\alpha }_{K-1}\end{array}\right]$
• this forms the core of the discrete fourier transform algorithm for finite length signals
• can be applied to elementary rotations of basis vectors in the euclidean plane
  • the same vector has different coefficients in the original and the rotates bases
  • the rotation matrix is obtained by the matrix multiplication of the original and the target bases
  • the rotation matrix applied to a vector in the original bases yields the coefficients of the same vector in the rotated bases
  • the matrix multiplication of the rotation matrix with its inverse yields the identity matrix

---

subspaces

• subspaces can be applied to signal approximation and compression
• with vector $\text{x}\in V$ and subspace $S\subseteq V$
  • approximate $\text{x}$ with $\hat{\text{x}}\in S$ by
  • take projection of the vector $\text{x}$ in $V$ on $S$
• due to the adaptation of vector space paradigm for signal processing
  • this geometric intuition for approximation can be extended to arbitrarily complex vector spaces

---

vector subspace

• a subspace is a subset of vectors of a vector space closed under addition and scalar multiplication
• classic example:
  • $R^2\subset R^3$
  • in-plane vector addition and scalar multiplication operations do not result in vectors outside the plane
  • $R^2$ uses only 2 of the 3 orthonormal basis of $R^3$
• the subspace concept can be extended to other vector spaces
  • $L_2[-1,1]$: function vector space
    • subspace: set of symmetric functions in $L_2[-1,1]$
    • when two symmetric functions are added, they yield symmetric functions
• subspaces have their own bases
  • a subset of their parent space’s bases

---

least square approximations

• ${{\text{s}}^{\left(k\right)}}_{k=0,1,\dots ,K-1}$ orthonormal basis for $S$
• orthogonal projection:
  • $\hat{\text{x}}={\sum }_{k=0}^{K-1}⟨{\text{s}}^{\left(k\right)},\text{x}⟩{\text{s}}^{\left(k\right)}$
• the orthogonal projection: the “best” approximation of $\text{x}$ over $S$ - because of two of its properties - it has minimum-norm error: - $argmi{n}_{y\in S}\parallel x-y\parallel =\hat{\text{x}}$ - orthogonal projection minimizes the error between the original vector and the approximated vector - this error is orthogonal to the approximation: - $⟨\text{x}-\hat{\text{x}},\hat{\text{x}}⟩=0$ - the error and the basis vectors of the subspace are maximally different - they are uncorrelated - the basis vectors cannot capture any more information in the error
• example: polynomial approximation
  • approximating from vector space $L_2[-1,1]$ to $P_N[-1,1]$
  • i.e. vector space of square-integrable functions to a subspace of polynomials of degree $N-1$
  • generic element of subspace $P_N[-1,1]$ has form
    • $\text{p}=a_0+a_{1}t+\dots +a_{N-1}{t}^{N-1}$
  • a naive, self-evident basis for this subspace:
    • ${\text{s}}^{\left(k\right)}=t^k,k=0,1,\dots ,N-1$
    • not orthonormal, however

---

approximation with Legendre polynomials

• example goal:
  • approximate $\text{x}=\sin t\in L_2[-1,1]$ to $P_3[-1,1]$
    • $P_3[-1,1]$: polynomials of the degree 2
• build orthonormal basis from naive basis
  • use Gram-Schmidt orthonormalization procedure for naive bases:
    • ${\text{s}}^{\left(k\right)}\to {\text{u}}^{\left(k\right)}$
    • ${\text{s}}^{\left(k\right)}$: original naive bases
    • ${\text{u}}^{\left(k\right)}$: orthonormalized naive bases
  • this algorithm takes one vector at a time from the original step and incrementally produces an orthonormal set
    1. ${\text{p}}^{\left(k\right)}={\text{s}}^{\left(k\right)}-{\sum }_{n=0}^{k-1}⟨{\text{u}}^{\left(n\right)},{\text{s}}^{\left(n\right)}⟩{\text{u}}^{\left(n\right)}$
       • for the first naive basis vector, normalize it with 1
       • project the second naive basis vector on to the normalized first basis
       • then subtract this projection from the second basis vector to get the second normalized basis
       • this removes the the first normalized basis’s component from the second naive basis
    2. ${\text{u}}^{\left(k\right)}=\frac{{\text{p}}^{\left(k\right)}}{\parallel \text{p}{\parallel }^{\left(k\right)}}$
       • normalize the extracted vector
  • this process yields:
    • ${\text{u}}^{\left(1\right)}=\sqrt{\frac{1}{2}}$
    • ${\text{u}}^{\left(2\right)}=\sqrt{\frac{3}{2}}t$
    • ${\text{u}}^{\left(3\right)}=\sqrt{\frac{5}{8}}(3t^2-1)$
    • and so on
  • these are known as Legendre polynomials
  • they can be computed to the arbitrary degree,
    • for this example, up to degree 2
• project $\text{x}$ over the orthonormal basis
  • simply dot product the original vector $x$ over all the legendre polynomials i.e. the orthogonal basis of the $P_3[-1,1]$ subspace
  • ${\alpha }_k=⟨{\text{u}}^{\left(k\right)},\text{x}⟩={\int }_{-1}^1{u}_k\left(t\right)\sin tdt$
    • ${\alpha }_0=⟨\sqrt{\frac{1}{2}},\sin t⟩=0$
    • ${\alpha }_1=⟨\sqrt{\frac{3}{2}}t,\sin t⟩\approx 0.7377$
    • ${\alpha }_2=⟨\sqrt{\frac{5}{8}}(3t^2-1),\sin t⟩=0$
• compute approximation error
  • so using the orthogonal projection
    • $\sin t\to {\alpha }_1{\text{u}}^{\left(1\right)}\approx 0.9035t$
    • this subspace has only one non-zero basis:
      • $\sqrt{\frac{3}{2}}t$
• compare error to taylor’s expansion approximation
  • well known expansion, easy to compute but not optimal over interval
  • taylor’s approximation: $\sin t\approx t$
  • in both cases, the approximation is a straight line, but the slopes are slightly different ($\approx$ 10% off)
    • the taylor’s expansion is a local approximation around 0,
    • the legendre polynomials method minimizes the global mean-squared-error between the approximation and the original vector
    • the error of the legendre method has a higher error around 0
    • however, the energy of the error compared to the error of the taylor’s expansion is lower in the interval
  • error norm:
    • legendre polynomial based approximation:
      • $\parallel \sin t-{\alpha }_1{\text{u}}^{\left(1\right)}\parallel \approx 0.0337$
    • taylor series based approximation:
      • $\parallel \sin t-t\parallel \approx 0.0857$

---

haar spaces

• haar spaces are matrix spaces
  • note: matrices can be reshaped for vector operations
• encodes matrix information in a hierarchical way
  • finds application in image compression and transmission
• it has two kinds of basis matrices
  • the first one encodes the broad information
  • the rest encode the details, which get finer by the basis index
• each basis matrix has positive and negative values in some symmetric pattern
• the basis matrix will implicitly compute the difference between image areas
  • low-index basis matrices take differences between large areas
  • high-index matrices take differences in smaller, localized areas
• this is a more robust way of encoding images for transmission methods prone to losses on the way
• if images are transmitted as simple matrices, they are prone to being chopped is loss in communication occurs during transmission

• haar encoding transmits coefficients not pixel by pixel but hierarchically in the level of detail
  • so if communication loss occurs, the broad idea of the image is still conveyed
  • while continued transmission will push up the detail level
• approximation of matrices to harr space is an example of progressive encoding

---

references

• Legendre Polynomial
• Ch 2: ‘From Euclid to Hilbert’ in Foundation of Signal Processing
• Flatland
• Haar wavelet transformation