singular value decomposition

[[concept]]

Topics

const fieldName = "theme"; // Your field with links
const oldPrefix = "Thoughts/01 Themes/";
const newPrefix = "Digital Garden/Topics/";
 
const relatedLinks = dv.current()[fieldName];
 
if (Array.isArray(relatedLinks)) {
    // Map over the links, replace the path, and output only clickable links
    dv.el("span",
        relatedLinks
            .map(link => {
                if (link && link.path) {
                    let newPath = link.path.startsWith(oldPrefix)
                        ? link.path.replace(oldPrefix, newPrefix)
                        : link.path;
                    return dv.fileLink(newPath);
                }
            })
            .filter(Boolean).join(", ") 
	// Remove any undefined/null items
    );
} else {
    dv.el(dv.current().theme);
}
 
 

Definitions

Theorem (Matrix Analysis 1)

Singular Value Decomposition

Let $A\in M_{m,n}$ such that $m\le n$. Then there exists $U\in M_n$ unitary, $\Sigma \in M_m$ diagonal, and $W\in M_{m,n}$ with orthonormal rows such that $A=U\Sigma W$

WLOG, we assume the diagonal elements of $\Sigma$ are nonnegative and ordered in a non-increasing.

$A{A}^{\ast }$ is hermitian and therefore positive semidefinite. So there exists $U\in M_n$ unitary and $D\in M_n$ diagonal such that $A{A}^{\ast }=UD{U}^{\ast }$ by the spectral theorem for hermitian matrices. Call the columns of $U=[u_1|u_2|\dots |u_m]$

Note that

Say each of the elements in $D$ are called ${\sigma }_{ii}^2\ge 0$ (we can do this because each eigenvector of $A{A}^{\ast }$ is real).

Say $A$ is rank $k$. Then let ${\sigma }_k>0,{\sigma }_{k+1}=0$ and define $\Sigma$ to be the $m\times m$ matrix containing the ordered ${\sigma }_i$s.

For $i=1,\dots ,k$, define the $i$th row of $W$ to be $\frac{1}{{\sigma }_i}{u}_i^{\ast }A$. These are orthonormal since for all $i,j$ we have $\frac{(}{1}{\sigma }_i{u}_i^{\ast }A)\frac{1}{{\sigma }_j{u}_j^{\ast }A}=u_i^{\ast }A{A}^{\ast }{u}_j=\frac{1}{{\sigma }_i{\sigma }_j}{D}_{ij}$ and this is $1$ if $i=j$ and $0$ otherwise.

For $i=k+1,\dots ,m$, define the rows of $W$ any way you like, so long as they are orthonormal and orthogonal to the first $k$ rows of $W$. And thus we are done! We have $U^{\ast }A=\Sigma W⟹A=U\Sigma W$

For rows $1,\dots ,k$ equality holds by construction. For rows $k+1,\dots ,m$, we have $A{A}^{\ast }{u}_i=0$ since each $u_i$ is an eigenvector with eigenvalues $0$ for $A{A}^{\ast }$. Thus we have $u_i^{\ast }A{A}^{\ast }{u}_i=0=||u_i^{\ast }A|{|}_2^2⟹u_i^{\ast }A=0=$ the $i$th row of $W$. So LHS = RHS = 0.

Note that if $A$ is real, we can take $U,\Sigma ,W$ real.

Theorem (Matrix Analysis 2)

Theorem (Singular Value Decomposition)

For any $A\in M_{m,n}$, there exists $U\in M_m$, $V\in M_n$ both unitary and $\Sigma \in M_{m,n}$ “diagonal” with $\min \{m,n\}$ real, nonnegative, nonincreasing, entries such that $A=U\Sigma V^{\ast }$

Further, if $A$ is real-valued, we can take each of $U,\Sigma ,V$ to be real.

(we take “diagonal” to mean that the only entries that can be nonzero have the same row and column index)

Note

• We can think of this as a generalization of diagonalization/spectral decomposition, but where the loss is that $U$ and $V$ are distinct.
• if $A$ is positive semidefinite, then the diagonalization is the singular value decomposition since we have that $A=U\Sigma U^{\ast }$ for some unitary $U$ and nonnegative $\Sigma$ all real.

$m\le n$, then by the previous definition here we have $A=U\Sigma W$ where $U\in M_n$ unitary, $\Sigma \in M_m$ diagonal, and $W\in M_{m,n}$ with orthogonal columns. Since $m\le n$, we add $n-m$ columns of zeros to $\Sigma$ to make it size $m\times n$. Then we can append $n-m$ orthogonal rows to $W$ with Gram-Schmidt to get a $V^{\ast }$

If

If $n>m$, then $A^{\ast }=U\Sigma V^{\ast }$ is SVD by the above case. But then $A=V{\Sigma }^T{U}^{\ast }$ is an SVD of $A$!

Another Definition (Data Science)

Singular Value Decomposition

The Singular Value Decomposition of a matrix $X\in {\mathbb{C}}^{n\times m}$ is the unique factorization such that $X=U\Sigma V^{\ast }$ Where $U\in {\mathbb{C}}^{n\times n},V\in {\mathbb{C}}^{m\times m}$ are unitary and orthonormal. A unitary matrix $U$ is one such that $U^{\ast }U=U{U}^{\ast }=I$. The columns of $U$ are called the left singular vectors of $X$, and the columns of $V$ are called the right singular vectors. The entries of $\Sigma$ are called the singular values

• the columns of $U$ are the same “shape” as the columns of $X$. They give me a basis where I can represent the columns of my data matrix $X$
  • This means that the columns of $U$ can be reshaped into “eigen”representations of instances of the data
• The columns of $V^{\ast }$ are the “mixtures” of the columns of $U$ that we need in order to reproduce each of the instances of the dataset

Notes on SVD

Say $A\in M_{m,n}$ and $A\in U\Sigma V^{\ast }$ its SVD. Suppose there are $k$ non-negative singular values call them ${\sigma }_1,\dots ,{\sigma }_k$. Denote $u_1,\dots u_m$ the columns of $U$ and $v_1^{\ast },\dots ,v_n^{\ast }$ the rows of $V^{\ast }$. Then

1. $A=U\Sigma V^{\ast }={\sum }_{i=1}^k{\sigma }_i{u}_i{v}_i^{\ast }$
2. $\text{rank}(A)=\text{rank}(\Sigma )=k$
3. $\text{range}(A)=\text{span}\{u_1,\dots ,u_k\}$ - easy to see from (1)
4. $\text{null}(A)=\text{span}(v_{k+1},\dots ,v_n)$ - easy to see from (1)
5. $\text{range}(A^{\ast })=\text{span}\{v_1,\dots ,v_k\}$
6. $\text{null}(A^{\ast })=\text{span}\{u_{k+1},\dots ,u_m\}$
7. For any $A\in M_{m,n}$, we have $||A|{|}_{2,2}:={\max }_{x\in {\mathbb{C}}^n\ne 0}\frac{||Ax|{|}_2}{||x|{|}_2}={\sigma }_1$
8. $||A|{|}_F^2=||U\Sigma V^{\ast }|{|}_F^2=||\Sigma |{|}_F^2={\sum }_{i=1}^k{\sigma }_i$

To see (5) and (6) , recall that $A^{\ast }=V{\Sigma }^T{U}^{\ast }$ and we simply apply (3) and (4) in this case.

To see (7), note that $||A|{|}_{2,2}^2={\max }_{x\ne 0}\frac{||Ax|{|}_2}{||x|{|}_2}=\max \frac{x^{\ast }{A}^{\ast }Ax}{x^{\ast }x}{=}^{\ast ,\ast \ast }{\sigma }_1^2$

• Note $\ast$ is by Rayleigh-Ritz that this equals the largest eigenvalue of $A^{\ast }A$.
• Then $\ast \ast$ is by the fact that the eigenvalues of $A^{\ast }A=(U\Sigma V^{\ast }{)}^{\ast }(U\Sigma V^{\ast })=V\Sigma {\Sigma }^{\ast }{V}^{\ast }$ - ie the eigenvalues are the squared singular values of $A$.

References

References

See Also

Mentions

Mentions

const modules = await cJS()
 
const COLUMNS = [  
	{ id: "Name", value: page => page.$link },  
	{ id: "Last Modified", value: page => modules.dateTime.getLastMod(page) },
];  
  
return function View() {  
	const current = dc.useCurrentFile();
// Selecting `#game` pages, for example. 
	let queryString = `@page and linksto(${current.$link})`;
	let pages = dc.useQuery(queryString);
	
	// check types
	pages = pages.filter( (p) => !modules.typeCheck.checkAll(p, current) ).sort()
	
	
	return <dc.Table columns={COLUMNS} rows={pages} paging={20}/>;  
}  

const { dateTime } = await cJS()
 
return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}