Let 
Theorem 19.1 (Geometric SVD) We have orthogonal decompositions
where 
In this theorem, “decomposition” really means two things: first, it refers to simultaneous orthogonal decompositions of the spaces 
where 
More precisely, 
or equivalently
This gives the Frobenius norm
or equivalently
We had a nice time proving early on, from first principles, that the Frobenius scalar product is in fact independent of the Cartesian coordinate systems in 
Now let us consider Theorem 19.1 from the point of view of Hilbert space geometry in
where
Proposition 19.2. 
Proof: Let 
Equivalently, the transformation 
Now compute the Frobenius norm of 
Similarly, suppose 
There are two mutually exclusive cases for the term in this sum corresponding to a given 
Now, the rank 
Proposition 19.3. For any 
Proof: By Proposition 19.2, this is an instance of the Pythagorean theorem.
A difficult and interesting question is to try to understand how the singular values of a sum 
which is a consequence of the fact that 
Proposition 19.4. For any
Proof: By Proposition 19.2, this is an instance of the Parallelogram Law.
are orthogonal one-dimensional subspaces of 
and the right singular lines 
are orthogonal one-dimensional subspaces in 
has the form 
with 
Corresponding to this, we have an “upstairs” decomposition
and 
In Lecture 19, we proved that 
of the Hilbert space ![[A]_{\{E_i\}}=\begin{bmatrix} \sigma_1 \\ \vdots \\ \sigma_r \\ 0 \\ \vdots \\ 0 \end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5BA%5D_%7B%5C%7BE_i%5C%7D%7D%3D%5Cbegin%7Bbmatrix%7D+%5Csigma_1+%5C%5C+%5Cvdots+%5C%5C+%5Csigma_r+%5C%5C+0+%5C%5C+%5Cvdots+%5C%5C+0+%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
the vector 
defined by 
![[A_q]_{\{E_i\}}=\begin{bmatrix} \sigma_1 \\ \vdots \\ \sigma_q \\ 0 \\ \vdots \\ 0 \end{bmatrix},](https://s0.wp.com/latex.php?latex=%5BA_q%5D_%7B%5C%7BE_i%5C%7D%7D%3D%5Cbegin%7Bbmatrix%7D+%5Csigma_1+%5C%5C+%5Cvdots+%5C%5C+%5Csigma_q+%5C%5C+0+%5C%5C+%5Cvdots+%5C%5C+0+%5Cend%7Bbmatrix%7D%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
Remembering that 
are morphism and not just inert vectors, we ask: what is the significance of 
as a linear transformation from 
morphisms in 
the transformation 
More precisely, if 
is any morphism of rank 
in Frobenius norm.
Our task is to demonstrate that if 
then
be a point in the Grassmannian of 
where 
is the orthogonal projection of 
is called the compression of 
and by construction it has rank 
It remains now to optimize the functional 
To do this we will express 
in terms of the singular data of 
and 
be ordered orthonormal bases adapted to the downstairs decompositions
and 
are orthonormal bases of 
are left singular vectors for 
are right singular vectors for 
in 
form an orthonormal basis of the kernel of 
in 
form an orthonormal basis for the complement of the image of 
we associate the compression numbers 
defined as the norms
is in fact independent of which unit vector 
we sample from the line 
since any other unit sample from 
with nonnegativity due to the fact that these numbers are norms, and the upper bound due to the fact that they are norms of projections of unit vectors. In fact, there is one more constraint on the compression numbers of a 
is at most the Frobenius norm of 
satisfy
realize the above maximizer, and that the corresponding compression is 
in total generality. It is perhaps surprising that this can be done; it is perhaps not surprising that it takes a couple of tries to get it right.
and any morphism 
of 
We know exactly how to compute 
for every 
the output is 
Unfortunately, the kernel is not a good starting point for a bootstrap understanding of an arbitrary linear transformation. First of all, if 
, and the statement 
is just part of what it means to be a linear transformation. Furthermore, even in the case where 
is nontrivial we learn nothing, and attempting to bootstrap from 
in 
into 
Restricting 
we are back in the injective situation. The dimension of the codomain 
of latex $V_0 = \mathrm{Ker}(A)$ and an orthonormal basis 
and take 
and 
we have ![[A] =\begin{bmatrix} 0 & [A]\end{bmatrix},](https://s0.wp.com/latex.php?latex=%5BA%5D+%3D%5Cbegin%7Bbmatrix%7D+0+%26+%5BA%5D%5Cend%7Bbmatrix%7D%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
![[A]](https://s0.wp.com/latex.php?latex=%5BA%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
has the same row echelon form as the external 
canonically associated to every morphism 
the space
a quantity bounded above by the operator norm 
. At the beginning of this week’s lectures we proved the following nontrivial theorem using the Parallelogram Law.
no matter what 
and 
. The first case means 
let 
be the image of 
Since 
the map 
is surjective by definition, and furthermore 
Let us write 
where 
Since 
is a nonzero scalar multiple of 
it is also surjective. Moreover, 
is an isometric isomorphism: the image of any orthonormal basis of 
under 
and the matrix of ![[U_1] = \begin{bmatrix} 1 & {} & {} \\ {} & \ddots & {} \\ {} & {} & 1\end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5BU_1%5D+%3D+%5Cbegin%7Bbmatrix%7D+1+%26+%7B%7D+%26+%7B%7D+%5C%5C+%7B%7D+%26+%5Cddots+%26+%7B%7D+%5C%5C+%7B%7D+%26+%7B%7D+%26+1%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
is ![[A_1] = \begin{bmatrix} 1 & {} & {} \\ {} & \ddots & {} \\ {} & {} & 1\end{bmatrix},](https://s0.wp.com/latex.php?latex=%5BA_1%5D+%3D+%5Cbegin%7Bbmatrix%7D+1+%26+%7B%7D+%26+%7B%7D+%5C%5C+%7B%7D+%26+%5Cddots+%26+%7B%7D+%5C%5C+%7B%7D+%26+%7B%7D+%26+1%5Cend%7Bbmatrix%7D%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
to be “exactly solved” should be noncontroversial. If you want a Euclidean image to hold in your mind, one option is the following: you can imagine 
as mapping 
on 
This means exactly that the transformation 
with 
and 
an isometric isomorphism. 
which is not the zero subspace of 
is the image of 
, which is a point of intrinsic interest: what is the relationship between the vectors which 
Indeed, if 
then we have
forces 
This says that any vector in 
is very straightforward: since 
we have 
which is equivalent to 
. Then, our decompositions
in 
This situation is important enough to warrant special terminology.
.
and
and 
.
with 
which remains to be analyzed, but has lower complexity than our original morphism 
where both the dimension of the domain and the rank of the morphism have strictly decreased – this is what failed to happen when we tried to bootstrap starting with 
i.e.
Note that since 
we have 
and the inequality is strict, as pointed out to me by Evan Young at least twice. If 
we are done: 
is the zero operator and we are back in the situation where 
Otherwise, 
and we define 
Then, the restriction of 
is a morphism 
of the form 
with 
an isometric isomorphism. As with our first pass, it remains to understand how 
in 
Structurally, we need to understand the decompositions 
is a subspace of 
. If 
then we are done: we have
which is a morphism 
of rank
we arrive at the Singular Value Decomposition.
the spaces 
are nonzero and the restriction of 
of the form 
with 
in the SVD are called the left and right singular spaces of 
of singular spaces may be zero. Indeed, 
, and the case 
occurs precisely when 
and 
we have orthogonal decompositions
sends a finite set 
to the free Hilbert space 
containing 
to the linear transformation 
whose action on this basis is
matches 
has no direct counterpart in 
In the classical computational category, you can identify a function 
with the ordered list of its fibers, but the fibers of 
which is literally a point of the domain of 
It is precisely this fact which allowed us to establish the Singular Value Decomposition for quantized set functions with no additional technology.
and 
. A function 
is![[A] = \begin{bmatrix} 0_{m \times n} & \mathcal{F}^*(f) \\ \mathcal{F}(f) & 0_{n \times m} \end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5BA%5D+%3D+%5Cbegin%7Bbmatrix%7D+0_%7Bm+%5Ctimes+n%7D+%26+%5Cmathcal%7BF%7D%5E%2A%28f%29+%5C%5C+%5Cmathcal%7BF%7D%28f%29+%26+0_%7Bn+%5Ctimes+m%7D+%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
and 
; write 
and 
Show that
which satisfies
exists, we want a geometric interpretation of it.
. However, it is not necessarily true that we can select 
such that our pre-selected 
by declaring its matrix elements to be what we want them to be. More precisely, set
and 
we have
is the nullity of 
is the corank of 
is the zero transformation. Now let us define a corresponding transformation 
by 
to 
for 
is the zero transformation into 
Deduce 
and 
defined by
is defined by inverting the invertible part of 
is an isomorphism onto 
with inverse 
holds in 
holds in 
No doubt you are familiar with the transpose of a matrix, so I will make the following remark: the transpose of the matrix of 
the corresponding matrices of 
Recall that for every finite dimensional Hilbert space 
, the space of linear functionals on 
from a vector space to a Hilbert space by defining the scalar product
consisting of the linear functionals 
defined by 
really is a linear transformation 
Taking orthonormal bases 
show that the matrix of 
and 
and 
and we can view 
there exists an isometric isomorphism 
such that 
it maps 
This fact will allow us to prove the Singular Value Decomposition geometrically, by induction on the rank of 
be any vector which is orthogonal to every vector 
We have to show that 
this is true simply because 
then we can assume without loss in generality that 
, again because 
is orthogonal to 
So, let 
be arbitrary, and consider the scalar product 
. First, let us show this under the following assumption.
, and consider the corresponding perturbation 
of the stretch optimizer 
As with every vector in 
the definition of 
and 
this becomes
for every 
which forces 
. (Hint: this is not hard, so don’t make it hard).
is strictly less than the rank of 
and orthogonal decompositions
for 
, whose objects are finite sets with morphisms being functions. Concretely, we are given finite sets 
Our objective is to choose orderings 
and 
of 
matrix ![[f]](https://s0.wp.com/latex.php?latex=%5Bf%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
of 
distinct fibers are disjoint, and the union of all fibers is 
In combinatorial parlance, the function 
-part set composition of 
, is the number of nonempty fibers of 
The type of 
with 
cells and 
and 
in any order, then listing the elements of 
and so on. Then, the matrix of 
which can be described explicitly as follows: the first row of 
entries equal to 
and all remaining entries equal to 
; the second row of 
entries equal to 
, and all remaining entries equal to 
entries equal to 
rows are all zero rows. 
we invoke the functor
For brevity let us write 
Thus, 
is a linear transformation with the special feature that
and 
may be even simpler than matrix of 
which is the binary matrix 
The capstone problem last week shows that we can construct an ordered orthonormal basis 
of 
,
nonzero entries. This is potentially much 
, the sparsity of 
.
and 
such that 
are an orthonormal basis for the kernel of 
for every 
is the operator norm of 
are those which are maximally stretched by applying 
, and observe that 
if and only if 
since we have already proved 
We then have
Now
To do so, it is sufficient to show that 
is a continuous function on 
whose supremum is 
By the Extreme Value Theorem, there exists 
such that 
whence 
of finite-dimensional Banach spaces.
whose source and target are finite-dimensional Hilbert spaces.
we showed that the matrix of 
Namely, we can choose orderings so that the matrix 
i.e. the “rank” of the set function 
For each 
the dimension of the corresponding block is the cardinality of the fiber 
be the linear transformation defined by
![\langle y,Ax \rangle = [x \text{ adjacent to }y], \quad x \in X,\ y \in Y.](https://s0.wp.com/latex.php?latex=%5Clangle+y%2CAx+%5Crangle+%3D+%5Bx+%5Ctext%7B+adjacent+to+%7Dy%5D%2C+%5Cquad+x+%5Cin+X%2C%5C+y+%5Cin+Y.&bg=FFFFFF&fg=000&s=0&c=20201002)
defined by
of 
and 
is the square root of the cardinality of the largest fiber of 
where 
is an 
unitary matrix, 
unitary matrix. Let’s check we got the dimensions right here: we write down the word 
and observe that matrix multiplication simplifies it to 
and then to 
which is indeed the shape of 
whose objects are finite sets and whose morphisms are functions. Let 
and let 
numbers![f_{yx} = [f(x)=y], \quad x \in X,\ y \in Y,](https://s0.wp.com/latex.php?latex=f_%7Byx%7D+%3D+%5Bf%28x%29%3Dy%5D%2C+%5Cquad+x+%5Cin+X%2C%5C+y+%5Cin+Y%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
![[P]=\begin{cases} 1, \text{ if }P\text{ true}\\ 0, \text{ if }P\text{ false} \end{cases}](https://s0.wp.com/latex.php?latex=%5BP%5D%3D%5Cbegin%7Bcases%7D+1%2C+%5Ctext%7B+if+%7DP%5Ctext%7B+true%7D%5C%5C+0%2C+%5Ctext%7B+if+%7DP%5Ctext%7B+false%7D+%5Cend%7Bcases%7D&bg=FFFFFF&fg=000&s=0&c=20201002)
![[f]_{ij} = f_{y_ix_j}, \quad 1 \leq i \leq m,\ 1 \leq j \leq n.](https://s0.wp.com/latex.php?latex=%5Bf%5D_%7Bij%7D+%3D+f_%7By_ix_j%7D%2C+%5Cquad+1+%5Cleq+i+%5Cleq+m%2C%5C+1+%5Cleq+j+%5Cleq+n.&bg=FFFFFF&fg=000&s=0&c=20201002)
the matrix 
it is tall and skinny (aka 
it is short and fat (aka 
so that possibly 
if and only if 
such that ![I_n = P[f]Q](https://s0.wp.com/latex.php?latex=I_n+%3D+P%5Bf%5DQ&bg=FFFFFF&fg=000&s=0&c=20201002)
if and only if 
matrix of zeros to the bottom of 
and an 
such that ![P[f]Q](https://s0.wp.com/latex.php?latex=P%5Bf%5DQ&bg=FFFFFF&fg=000&s=0&c=20201002)
is in this canonical form if and only if 
Now letting 
with edges going between two disjoint sets of vertices 
is an edge if and only if 
The connected components of 
are 
in which the hub vertex 
has degree equal to the cardinality 
of the fiber of 
The surjectivity condition means that each of these star graphs has at least one edge or, equivalently, two vertices. The type of 
whose components are the positive numbers
is a 
and let 
be an ordering of its elements. Let 
and let 
be an ordering of its elements. Let 
The matrix of this function with respect to these ordering is![[f]=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5Bf%5D%3D%5Cbegin%7Bbmatrix%7D+1+%26+1+%26+1+%26+0+%26+0+%5C%5C+0+%26+0+%26+0+%26+1+%26+1+%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
and let 
be an ordering of its elements. Let 
be an ordering of its elements. Let 
The matrix of this function with respect to these ordering is![[f]=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1\end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5Bf%5D%3D%5Cbegin%7Bbmatrix%7D+1+%26+1+%26+1+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+1+%26+1+%26+0+%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+1%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
from finite sets to finite 
is containment, meaning that for 
we define
and the largest set contained in both 
respectively.
and 
bijectively onto 
which is why
we have 
is not complete until we say where it sends a given set function 
. The corresponding 
is defined by = f(Y) = \{f(x) \colon x \in y\}.](https://s0.wp.com/latex.php?latex=%5B%5Cmathcal%7BP%7D%28f%29%5D%28Y%29+%3D+f%28Y%29+%3D+%5C%7Bf%28x%29+%5Ccolon+x+%5Cin+y%5C%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
really is a morphism in 
is said to be a 
for all 
and 
for all 
whose objects are 
in 
consisting of a finite set 
a specific retraction 
of 
denote the subgroup of 
consisting of all automorphisms (permutations) 
of 
Call a rule 
which assigns to set/subset pairs a corresponding retraction canonical if 
and 
is nonempty, no canonical retraction exists. 
Then, for every 
we have 
to be fixed by every permutation of 
a contradiction. 
Then, for any nonempty 
we can define a retraction of 
to be the point of 
However, even here we need to impose a rule for breaking ties (two distinct minimizers). Once we do this, the retraction 
which preserve tie breakers.
Conversely, show that if 
denote the set of idempotent functions in 
. Define an equivalence relation on 
![[f]_Y = \{f \in \mathrm{End}(X) \colon \mathrm{Im}(f)=Y,\ f^2=f\}.](https://s0.wp.com/latex.php?latex=%5Bf%5D_Y+%3D+%5C%7Bf+%5Cin+%5Cmathrm%7BEnd%7D%28X%29+%5Ccolon+%5Cmathrm%7BIm%7D%28f%29%3DY%2C%5C+f%5E2%3Df%5C%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
![Y \mapsto [f]_Y](https://s0.wp.com/latex.php?latex=Y+%5Cmapsto+%5Bf%5D_Y&bg=FFFFFF&fg=000&s=0&c=20201002)
is a bijection 
defined by 
is a bijection (binary encoding of subsets). 
inside of which 
only includes subsets of 
The meet and join operations in 
is a linear transformation the corresponding order homomorphism 
is defined by  = A(W) = \{Aw \colon w \in W\} = \mathrm{Im}(A).](https://s0.wp.com/latex.php?latex=%5B%5Cmathcal%7BL%7D%28A%29%5D%28W%29+%3D+A%28W%29+%3D+%5C%7BAw+%5Ccolon+w+%5Cin+W%5C%7D+%3D+%5Cmathrm%7BIm%7D%28A%29.&bg=FFFFFF&fg=000&s=0&c=20201002)
antichains
Although each 
is uncountably infinite set, it has much more structure than just being a very big set. In fact, these sets are important enough that they have a special name.
quantizes to 
giving 
special subspaces of 
Complementary subsets of 
Moreover, prove that we have the internal direct sum decomposition 
is a coordinate subspace of 
the line in 
does not contain any point of 
(Hint: you can deduce this directly from Problem 10.3 by constructing an appropriate unitary operator on 
a linear retraction of 
such that 
and the restriction of 
to 
is a retraction onto its image if and only if it is idempotent, 
denote the set of idempotent operator on ![W \mapsto [P]_W](https://s0.wp.com/latex.php?latex=W+%5Cmapsto+%5BP%5D_W&bg=FFFFFF&fg=000&s=0&c=20201002)
which sends a subspace 
to the equivalence class ![[P]_W](https://s0.wp.com/latex.php?latex=%5BP%5D_W&bg=FFFFFF&fg=000&s=0&c=20201002)
of idempotent operators with image 
or 
In the quantum setting, given a vector 
is or is not 
with 
such that 
That is, we have 
where 
For any vector 
consider its expansion in the orthonormal basis 
We claim that 
and that 
is the unique point of 
unless we have
and that 
![[f]_Y](https://s0.wp.com/latex.php?latex=%5Bf%5D_Y&bg=FFFFFF&fg=000&s=0&c=20201002)
of idempotents with image 
i.e. 
Let 
and for any 
That is, the orthogonal projection 
as its diagonal.
meaning that we would have to compute its image 
and check that 
In fact, there is an algebraic characterization of which idempotents actually are orthogonal projections: it is precisely the selfadjoint ones. I mention this because you probably already know it. If you don’t that’s even better, because we will prove this characterization as a theorem after we establish the singular value decomposition, which we shall use to define the