Diffusion wavelets

This algorithm constructs the scaling basis functions and the wavelet basis functions along with the representations of the diffusion operator ${\displaystyle T}$ at these scales.

In the algorithm below, the subscript notation ${\displaystyle \Phi _{a}}$ and ${\displaystyle \Psi _{b}}$ represents the scaling basis functions at scale ${\displaystyle a}$ and the wavelet basis functions at scale ${\displaystyle b}$ respectively. The notation ${\displaystyle [\Phi _{b}]_{\Phi _{a}}}$ denotes the matrix representation of the scaling basis ${\displaystyle \Phi _{b}}$ represented with respect to the basis ${\displaystyle \Phi _{a}}$. Lastly, the notation ${\displaystyle [T]_{\Phi _{a}}^{\Phi _{b}}}$ denotes the matrix represents of the operator ${\displaystyle T}$, where the row space of ${\displaystyle T}$ is represented with respect to the basis ${\displaystyle \Phi _{a}}$, and the column space of ${\displaystyle T}$ is represented with respect to the basis ${\displaystyle \Phi _{b}}$. Otherwise put, the domain of operator ${\displaystyle T}$ is represented with respect to the basis ${\displaystyle \Phi _{a}}$ and the range is represented with respect to the basis ${\displaystyle \Phi _{b}}$. The function ${\displaystyle QR}$ is a sparse QR decomposition with ${\displaystyle \epsilon }$ precision.[2]

// Input:
//    ${\displaystyle T}$ is the matrix representation of the diffusion operator.
//    ${\displaystyle \epsilon }$ is the precision of the QR decomposition, e.g., 1e-6.
//    ${\displaystyle J}$ is the maximum number of scale levels (note: this is an optional upper bound, it may converge sooner.)
// Output:
//    ${\displaystyle \lbrace \Phi _{j}\rbrace }$ is the set of scaling basis functions indexed by scale ${\displaystyle j}$.
//    ${\displaystyle \lbrace \Psi _{j}\rbrace }$ is the set of wavelet basis functions indexed by scale ${\displaystyle j}$.
  
${\displaystyle \lbrace \Phi _{j}\rbrace ,\lbrace \Psi _{j}\rbrace \leftarrow {\text{function DiffusionWaveletTree}}(T,\epsilon ,J):}$
    ${\displaystyle {\textbf {for}}j\leftarrow 0{\text{ to }}J-1}$:
        ${\displaystyle [\Phi _{j+1}]_{\Phi _{j}},[T^{2^{j}}]_{\Phi _{j}}^{\Phi _{j+1}}\leftarrow QR\left([T^{2^{j}}]_{\Phi _{j}}^{\Phi _{j}},\epsilon \right)}$
        ${\displaystyle [T^{2^{j+1}}]_{\Phi _{j+1}}^{\Phi _{j+1}}\leftarrow \left([T^{2^{j}}]_{\Phi _{j}}^{\Phi _{j+1}}[\Phi _{j+1}]_{\Phi _{j}}\right)^{2}}$
        ${\displaystyle [\Psi _{j}]_{\Phi _{j}}\leftarrow QR\left(I_{\langle \Phi _{j}\rangle }-[\Phi _{j+1}]_{\Phi _{j}}\left([\Phi _{j+1}]_{\Phi _{j}}\right)^{*},\epsilon \right)}$ 
    ${\displaystyle {\textbf {endfor}}}$

• Wavelets

• Mauro Maggioni's MATLAB code implementation
• Chang Wang's diffusion wavelet page