Category Archives: 202A

A key concept is that there is a third fundamentally important subspace associated to every morphism . Unlike and this subspace is geometric rather than algebraic in nature: it is defined as the set

of vectors in which saturate the operator norm inequality for It is not obvious that this actually is a vector space, and the following result is both crucial and nontrivial.

Theorem 5.1. is a nonzero subspace of

The fact that contains a unit vector follows from the extreme value theorem. We found a way to use the parallelogram law to show that is a subspace of The essence of the singular value decomposition is understanding the relationship between the three fundamental subspaces

a geometric endeavor which goes beyond the algebraic relationship between kernel and image given by the rank-nullity theorem. In order to succeed in this question, one needs the following fact.

Orthogonality Lemma. Two nonzero vectors are orthogonal if and only if for all .

Proof: Geometrically, the Orthogonality Lemma says that are orthogonal if and only if the point on the affine line closes to is . In fact, this characterization remains correct even in the infnite-dimensional setting.

Suppose first that and are orthogonal. Then, for any scalar we have

Conversely, suppose that the nonnegative function

is minimized by taking the minimum being Suppose and look at

We then compute

a contraction.

Armed with the Orthogonality Lemma, we turn to an examination of the geometric relationships between the three fundamental subspaces of a linear transformation. The first such relationship is the nice fact that maximally stretched vectors are orthogonal to squashed ones.

Theorem 5.2. Assuming we have

Proof: Since is a nonzero subspace of , we can choose a nonzero vector If the kernel of is trivial, the statement we want to prove is obvious. If not, we can choose a nonzero vector . Now use the Orthogonality Lemma on the affine line

Now let us see how Theorem 5.2 refines what the rank-nullity theorem tells us. We have the orthogonal decompositions

Rank-nullity says that the restriction of to a morphism is an isomorphism. Theorem 5.2 tells us that sitting inside we have the space of maximally stretched vectors. The best case scenario is that exhausts Then, we learn that the isomorphism is almost an isometric isomorphism: it is times the isometric isomorphism given by If we are not so lucky, then we have

where the orthogonal complement of inside is a nontrivial subspace of Now we have to try again: this is the start of an iterative process which terminates after finitely many steps, the output being the Singular Value Decomposition, which is adequately treated in the main notes. If you understand this process, you understand everything about linear algebra that you need to know for Math 202A.

The next stage in our comparison of the classical computational category and the quantum computational category focused on contrasting with We have seen already that

which is a polynomial function of and an exponential function of Of course, the cardinality of is infinite, but its quantum cardinality,

is a linear function of and a linear function of

We now consider subobjects canonically associated to morphisms in and

Associated to a morphism is its image,

which is a subset of the target The cardinality of may be called the rank of the set function The rank of is bounded by the cardinality of its source and we have if and only if is injective. The rank of is also bounded by the cardinality of its target , and we have if and only if is surjective. Thus,

A morphism is said to have full rank if

In particular, a full rank function is either injective or surjective, but we cannot say which without knowing which of is larger. On the other hand, the concept of rank itself is an elementary combinatorial notion, and one can find an explicit formula for the number of rank morphisms in in terms of Stirling numbers. Using this formula, one can show that the set of full rank morphisms in is small in comparison to the total cardinality

Associated to a morphism is its image,

which is a subspace of the target space The rank of the linear transformation is the dimension of . The rank of is bounded by the dimension of and this bound is achieved if and only if is injective. The rank of is bounded by the dimension of , and this bound is achieved if and only if is surjective. Thus,

A morphism is said to have full rank if this upper bound is achieved, and just like in the classical situation this means either that is injective or surjective, but we cannot determine which without more information. What is very different in the quantum world is that a generic morphism in has full rank.

Theorem 4.1. The set of full rank morphisms in is open and dense in the norm topology.

Note that we have two norms on the operator norm and the Frobenius norm, and we did not specify which is being used in Theorem 4.1. This is because these two norms generate the same topology, as do all norms on a finite-dimensional vector space.

Theorem 4.1 is another way to motivate the long journey we took towards the Singular Value Decomposition. The first step on this journey is to recognize that the there is a second subobject associated to which has no classical counterpart, namely the kernel

which is a subspace of The dimension of is called the nullity of and denoted

For an arbitrary morphism , we have two affiliated spaces: and Consider the associated orthogonal decompositions,

The rank-nullity theorem says that the restriction of to is an isomorphism onto This result is purely algebraic, and does not involve in the Hilbert space structure on and . The Singular Value Decomposition may be viewed as a remarkable refinement of the rank-nullity theorem which uses the geometric structure of Hilbert space to achieve a much more precise description of morphisms in

A nice observation we made is that one can guess what this mysterious enhanced decomposition looks like for morphisms which are quantizations of set maps, i.e. the case where for In this case, using purely combinatorial reasoning, one can construct an orthonormal basis for and an orthonormal basis for such that the restriction of to an isomorphism has a very explicit description in terms of the combinatorial statistics of the underlying set function It is useful to review this combinatorial “bare hands” special case of the SVD for quantized set functions before starting down the geometric road to developing it for arbitrary morphisms in

After setting up the dichotomy between the classical computational category and the quantum computational category we started to compare the two. This comparison begins with matrices: matrices over suffice to encode both objects and morphisms in , whereas matrices over are needed to encode objects and morphisms in but the encoding works the same way. Change of ordering in the one-hot encoding of a finite set is implemented by left multiplication by permutation matrices, whereas change of orthonormal basis in a finite-dimensional Hilbert space is implemented by left multiplication by unitary matrices; in this sense, unitary matrices are the quantum generalization of permutation matrices. Change of ordering in the source and target sets of corresponds to left and right multiplying the matrix encoding of morphisms by permutation matrices, while change of ordered orthonormal bases in the source and target spaces of corresponds to left and right multiplying the matrix encoding of morphisms by unitary matrices.

A more interesting line of investigation is to consider the extent to which can be enriched beyond i.e. made into something more than a set. First, the existence of a vector space structure on is very straightforward, and in fact a special case of the fact that the set of functions from any set into a vector space is again a vector space under the pointwise operations.

It is also true that is finite-dimensional. Let and be orthonormal bases, which is the same thing as saying is isomorphic to and is isomorphic to What we showed is that is isomorphic to Indeed, for each define a corresponding elementary transformation by

We proved that is a basis of and indeed that for any we have

This is a good way to present the information contained in the matrix of relative to the orthonormal bases and without having to choose orderings just to write things in an array.

The elementary basis of relative to a pair of orthonormal bases and also gives us a convenient way to analyze topological properties of arbitrary morphisms Indeed, for any we have that

where the inequality is Cauchy-Schwarz and we used the fact that and are unit vectors. Thus, each morphism in the elementary basis of is a contractive mapping. Thus for an arbitrary morphism

the triangle inequality gives us

where

is a norm on , specifically the -norm relative to the elementary basis of , which is itself defined relative to the orthonormal bases and This points us to a much better norm on since the above tells us that every is not just continuous but Lipschitz, with Lipschitz constant bounded by

Definition 3.1. The operator norm of is by definition its Lipshitz constant.

One of the many virtues of the operator norm is that it is basis independent: to define it we only need to know that all morphisms in are Lipschitz functions. Definition 3.1 does not care that we used orthonormal bases of and to establish Lipschitz continuity of linear transformations. On the other hand, one could argue that a demerit of the operator norm is that it is not induced by a scalar product.

Problem 3.1. Prove that there is no scalar product on such that coincides with the operator norm.

On the other hand, it is completely straightforward to promote to a Hilbert space: we simply equip it with the scalar product in which forms an orthonormal basis. This is the Frobenius scalar product on , and it is given explicitly as follows: for any we have

Problem 3.2. Show that for any we have

The norm on obtained from the Frobenius scalar product is called the Frobenius norm, and denoted

The problem with the above is that we don’t know whether we have built the Frobenius scalar product or a Frobenius scalar product: if we had performed this construction using two different orthonormal bases and would we have arrived at the same Hermitian form on ? We would like to know whether is basis independent, like the operator norm , or whether it is basis dependent, like

The answer is that the Frobenius scalar product is basis independent. A morphism such that for every is called an isometry. Polarization shows that norm preservation is the same as scalar product preservation: is an isometry if and only if

Furthermore, every isometry is injective, so that an isometry in is automatically an automorphism. Isometric automorphisms of are also referred to as unitary operators. That’s right, there are two names for the same thing. While it might be better practice to never ever override general categorical terminology in category-specific settings, this is just one of many things about the world that could be improved. Even worse, if and are possibly different finite-dimensional Hilbert spaces with then again an isometry is automatically an isomorphism, and such isometric isomorphisms are also often called unitary transformations. Saints preserve us. The reason for this abuse of terminology is that the matrix of an isometric isomorphism is a unitary matrix even when the spaces are not the same, just like the matrix of set isomorphism is a permutation matrix even when and are distinct sets.

Problem 3.3. Show that is a unitary operator if and only if the image of an orthonormal basis under is an orthonormal basis of .

Problem 3.2 already removes the dependence of the Frobenius scalar product on a choice of orthonormal basis in the target space. Thus what is left to check is that for any orthonormal basis and any unitary operator we have

In other words, thanks to polarization, we only need to check that the Frobenius norm is unitarily invariant. We have

Thus,

and to finish it remains only to establish the following, which is a consequence of Problem 3.3.

Problem 3.4. For any unitary operator and any orthonormal basis we have

In the lectures I presented a different proof of unitary invariance of the Frobenius scalar product on which was inductive in the dimension of The reason for doing this was that in the base case, we are dealing with the dual space of and this leads to a discussion of vectors and covectors (Riesz duality). However, I did not do a very good job with this discussion and therefore have decided to leave it out of the exam topics.

Let be the category whose objects are complex vector spaces equipped with a scalar product and whose morphisms are linear transformations. We call pairs Hilbert spaces, and our convention is that the scalar product is linear in the second slot. The standard definition of Hilbert space includes an extra clause which we do not need and will omit (see below),

Problem 2.1. Prove that is an isomorphism if and only if it is a bijection. That is, isomorphisms in are precisely linear bijections.

The Hilbert space norm on is defined by

To prove that this really is a norm, one needs the Cauchy-Schwarz inequality in order to verify the triangle inequality,

Problem 2.2. Prove the reverse triangle inequality: . Make sure you understand why this implies that the function defined by is continuous, in fact -Lipschitz.

An important fact is that the scalar product in a Hilbert space can be recovered from the norm.

Theorem 2.3. (Polarization) For any we have

Two vectors in Hilbert space are said to be orthogonal if

Theorem 2.4. (Pythagoras) For any orthogonal vectors , we have

An important generalization of the Pythagorean theorem is the following.

Theorem 2.5 (Parallelogram Law) For any we have

Much of the importance of the Parallelogram Law is that it characterizes when a normed vector space is a Hilbert space. This remarkable fact was first noticed by von Neumann.

Problem 2.3. If is a complex vector space equipped with a norm then there exists a scalar product on such that if and only if the Parallelogram Law holds.

The standard definition of Hilbert space includes an extra completeness condition which we was not used above, and will not be used going forward. Therefore, we omit this condition from our definition of what constitutes a Hilbert space.

We define the quantization functor

as follows. First, for every finite set we declare

to be the vector space of complex-valued functions on together with the scalar product

Second, if are finite sets and is a function, then we declare to be the linear transformation defined by

In words, is the sum of the values of over the points in the fiber of over Assuming are disjoint, you can visualize this by associating to the bipartite graph with vertex set and edges given by input-output pairs of . This bipartite graph is a disjoint union of star graphs: each star consists of a hub vertex and the remaining vertices of the star are the points of which map to via The function acts on by summing the values of over non-hub vertices.

Problem 2.4. Prove that finite sets and are isomorphic if and only if the Hilbert spaces and are isomorphic.

Now let us explain why we refer to as the quantization functor. For each the corresponding elementary function is defined by

A basic feature of these functions is their orthogonality,

Theorem 2.6. For any , there exist unique scalars such that

Proof: To prove existence, check that works. For uniqueness, imagine we have two such representations of and then use evaluations of to show these representations are the same.

Theorem 2.6 allow us to develop an alternative perspective which is widely used in algebra: we view complex-valued functions on as formal -linear combinations of its points,

This is really just notation, and one should remember that the expression above is just a different way of writing down the function , The formal linear combination perspective on functions is also widely used in physics. A set for example the natural set can be viewed as the state space of a particle on the integer lattice which may be located at any of the sites . The particle is “classical” in the sense of classical mechanics: it has a definite location, which may be any of the sites A quantum particle does not have a definition location: before it is observed, it exists simultaneously in each of the states , and only after it is observed does its location become definite. A (pure) quantum state is a formal linear combination

of classical states such that

where the amplitude is the probability that will be in state once it is observed. Thus, (pure) quantum states are the same thing as unit vectors in the Hilbert space In applying the functor , we are passing from the state space of a classical particle to the state space of a quantum particle.

Mathematically, many features of Hilbert space can be viewed as quantum generalizations of familiar set-theoretic properties. For example, let and be two subsets of and let

be their indicator functions in whose norms are and If and are disjoint, then and are orthogonal in , and the Pythogorean theorem

reproduces However, the Pythagorean theorem holds for all pairs of orthogonal vectors in , not just indicator functions of disjoint subsets of Similarly, the Parallelogram Law can be seen as a quantum generalization of the inclusion-exclusion principle.

Definition 2.7. A Hilbert space is said to be finite-dimensional if there exists a finite set such that is isomorphic to Otherwise, it is said to be infinite-dimensional.

This definition is non-traditional, but it has certain advantages. In particular, thanks to Problem 2.4 we can define the dimension of a finite-dimensional Hilbert space to be the cardinality of any finite set such that is isomorphic to

Problem 2.4. Prove that finite-dimensional Hilbert spaces and are isomorphic if and only if they have the same dimension.

A more traditional approach to dimension is based on the following definition.

Definition 2.8. A finite set of vectors in a Hilbert space is said to be linearly independent if

It is easy to see that any finite orthonormal set is linear independent. The converse is also true.

Proposition 2.9. (Gram-Schmidt) If contains a linearly independent set of cardinality , then it contains an orthonormal set of cardinality

From here we establish the equivalence of Definition 2.7 and the standard definition of dimension.

Theorem 2.10. A Hilbert space has dimension if and only if it contains an orthonormal set of cardinality and does not contain an orthonormal set of cardinality

Let be the category whose objects are sets and whose morphisms are functions. In more detail, for any two sets and let be their Cartesian product and let be the power set of . Then is the subset of defined by the condition

In particular, is a locally small category. Going forward we will use the standard functional notation to denote

A function is said to be injective if

and surjective if

where A function which is both injective and surjective is called bijective.

Problem 1.1. Prove that two sets are isomorphic if and only if contains a bijection.

A natural set is a set of the form where is a natural number. By Problem 1.1, two natural sets and are isomorphic if and only if in which case Thus, the full subcategory of whose objects are natural sets is a skeletal category.

Definition 1.1. A set is said to be finite if it is isomorphic to a natural set.

Since is skeletal, this means that there is one and only one natural number such that contains an isomorphism. This natural number is called the cardinality of the finite set and we write Let be the full subcategory of whose objects are finite sets.

Problem 1.2. Given finite sets and with and prove that is a finite set and calculate its cardinality.

Problem 1.2 shows that the category is enriched over itself. is called the classical computational category because its objects and morphisms can be encoded using classical bits, and thus instantiated on a computer. The adjective “classical” is used to contrast with the quantum computational category, whose objects and morphisms can presumably be instantiated on a quantum computer.

We will construct the quantum computational category in Lecture 2. In the remainder of Lecture 1, we focus on encoding objects and morphisms in Let and be natural numbers, and let be a set, not necessarily finite.

Definition 1.2. An matrix over is an element of

Given a matrix , the notation is used for its values, and we write instead of for the set of matrices over This is because matrices are typically thought of as two-dimensional arrays populated by elements of

Matrices are called column matrices because they are visualized as arrays consisting of a single column,

while matrices are called row matrices because they are visualized as arrays consisting of a single row,

While these visualizations are very convenient, one should remember that an matrix over is really a function in

Classical computation utilizes matrices over which are called binary matrices. Since is a finite set, binary matrices are morphisms in Let be a set of cardinality . Then contains an isomorphism , and hence contains an isomorphism An isomorphism is referred to as an ordering of and we write

Using this enumeration of the elements of , we can define an injective function by

The injection is called the one-hot encoding of relative to the ordering and the output is called the column matrix of relative to this ordering.

Now let and be two sets of cardinalities and respectively, and let and be orderings of these sets. Using these orderings, we can define an injective function by

The injection is called the binary encoding of relative to the orderings and . The definition of may be equivalently stated as follows: for each column of is the one-hot encoding of relative to the ordering of

Now let be three finite sets of cardinalities respectively. Let and and be orderings of these sets. Let and be given functions, and let be their composition. We want to understand the relationship between the matrices

of the functions and relative to the given orderings of

Problem 1.3. Prove that the matrix defined by

in fact belongs to and that

Let be a morphism with left and right singular blocks

and let be the corresponding singular values: the restriction of to has the form where is an isometric isomorphism. As a decomposition of itself, we have

where is the orthogonal projection of onto the left singular block . We have seen previously that is an orthogonal set in with respect to the Frobenius scalar product: we have

In particular, we have the Frobenius norm

Previously, we wrote this in terms of repeated singular values, meaning that we decomposed each and into a direct sum of orthogonal lines instead of incorporating the multiplicity factor The two ways of thinking about the SVD — blocks and lines — are both correct, but we have to keep in mind that the block decomposition is unique whereas the line decomposition is only unique when the number of singular values is equal to the rank of In particular, if we want to use the SVD to define the adjoint, we should use the block version.

Definition 22.1. The adjoint of is the morphism defined by

where is the orthogonal projection of onto the right singular block

A particularly simple (but important) situation is when comes to us as an isometric isomorphism. Then, the singular value decompositions of and are

the singular value decomposition of is

and

It is clear from Definition 22.1 that the adjoint is an involution, Geometrically, this just says that swapping left and right singular blocks twice is the same as not swapping them at all.

Now we consider the case where the source and target spaces of coincide, meaning that and In this setting there are two further coincidences that could potentially occur: the left and right singular blocks of could coincide, or could coincide with its adjoint, In the first case we say that is normal, and in the second we say that is selfadjoint. A priori, it is not clear what the relationship between normality and selfadjointness might be. Of course, we already know the answer from prolonged exposure to matrix algebra.

Theorem 22.2. Selfadjoint implies normal.

I would like to give a geometric proof of the fact that selfadjointness,

implies normality,

This amounts to showing that

forces in , for each I have not yet succeeded in finding such an argument, and while I plan to try again on my own time you may be getting tired of me constantly turning things upside down and inside out and generally treating linear algebra results we can look up as if they were open research problems. If so, you may have given up on Math 202A, which is fine with me provided you are working on the mathematics that matters to you. I mean this sincerely and will extend the following provision: if you have fallen behind on 202A homework sets because you are composing your mathematical opus, you can turn in that work for homework credit in 202A.

Look up the definition of a normal matrix in any textbook and you’ll get an algebraic characterization of normality which makes Theorem 22.2 obvious.

Theorem 22.3. is normal if and only if

Problem 22.1. Prove that selfadjoint implies normal. You have two options: either find the direct geometric argument I failed to produce, or prove the standard result Theorem 22.3 and deduce the claimed implication from it.

Now, on to the spectral theorem. Assume is selfadjoint. Then, because is normal, its left and right singular blocks coincide. The SVD tells us that the restriction of to the singular block is

where is an isometric automorphism of , aka a unitary operator on The same reasoning applied to gives

Since we have

and since we can cancel it to get

In summary, the SVD is reducing the study of selfadjoint operators to the study of unitary selfadjoint operators: we have shown that being selfdadjoint means that

where is both selfadjoint and unitary. So let us step back and consider the highly constrained problem of analyzing a selfajdoint unitary operator

Since is unitary, , and since is selfadjoint, Combining these gives and we conclude that a selfadjoint unitary operator satisfies

where is the identity operator on Two obvious solutions to this equation are and latex and in fact all solutions are mixtures of these two. More precisely, let

and

Theorem 22.4. We have

Note that it is *not* necessarily true that both and are nonzero subspaces, as the examples and already show.

Now return to the general situation, where we know that is selfadjoint, but we are not assuming it is also unitary. What we do know is that

where the restriction of to is with selfadjoint and unitary. This gives us the decomposition

where acts in as multiplication by acts in as multiplication by In words, the condition that allows us to refine its SVD by decomposing each singular block into a positive part and a negative part and since is not the zero space at least one of is nonzero.

Theorem 22.5. (Spectral Theorem) Given selfadjoint, there exists an orthogonal decomposition

where are nonzero subspaces such that

where are nonzero real numbers. Each is a signed singular block of and each is a signed singular value of

Given a morphism we have discussed extensively the singular value decomposition of .

Theorem 21.1. (Geometric SVD, block form) There exists a positive integer , distinct positive numbers and orthogonal decompositions

such that the restriction of to equals where is an isometric isomorphism.

The spaces are the left singular blocks of the spaces are the right singular blocks of and the numbers are the singular values of and the set is the singular spectrum of

Problem 21.1. Give a precise formulation and proof of the following statement: the block SVD of a linear transformation is unique. (Hint: one way to write this down formally is using Fermat’s method of infinite descent. Suppose there do exist morphisms which admit two distinct SVDs. Let be the minimal rank of such a morphism. Prove that the first singular block and singular value in these two decompositions must be the same. Then, the non-uniqueness comes from the restriction of this morphism to the orthogonal complement of the first singular block, which has lower rank; contradiction).

For each the positive number is the multiplicity of the singular value and if this number is equal to one we say that is a simple singular value of If all singular values of are simple, then we say that has simple singular spectrum; this means precisely that has distinct singular values . In this case, the left singular blocks are one-dimensional subspaces and we call them the left singular lines of Likewise, are one-dimensional subspaces of the right singular lines of It is often useful to employ this perspective even when does not have simple singular spectrum.

Theorem 21.2. (Geometric SVD, line form) There exist positive numbers

such that the restriction of to equals where is an isometric isomorphism.

When the block and line forms of the SVD are literally the same statement. However, when , they are not, because the line form becomes ambiguous: there is at least one such that we are decomposing each of the singular blocks into a direct sum of orthogonal lines, and these decompositions can be performed arbitrarily and independently. I have generally been pretty sloppy about accounting for this, because it almost never happens.

Theorem 21.3. (Generic simplicity) The set of morphisms with simple singular spectrum is a dense open set in

Proof: Proving this is definitely my job, and I am still thinking about how to present the simplest and most elegant argument. Here is the basic idea. First, notice that I did not specify a norm on in the statement. This is intentional: the vector space is finite-dimensional, so all norms are equivalent (note to self: go back and prove this in the discussion of norms on Hilbert space), and since density is a topological as opposed to geometric property (closure equals whole space) we are free to choose whichever norm is the most convenient. The best choice is operator norm, since this allows us to construct an infinite descent argument compatible with the iterative construction of the SVD based on repeatedly saturating the operator norm; this is similar in spirit to the one used to verify uniqueness of the block SVD. Namely, since the block SVD is constructed iteratively by looking for vectors which saturate the operator norm inequality, we can reduce to verifying that the set of transformations such that is one-dimensional is an operator norm dense open set in which is actually not too difficult. (Note to student: if you can either fine-tune this argument, or find a better one, please show me your approach).

Theorem 21.3 means that every time I am being sloppy about non-uniqueness of the line SVD, I am being sloppy on the complement of a dense open set, and such sets do not have civil rights. In the remainder of the lecture I will continue doing this instead of altering all statements to account for the possibility of repeated singular values. The actual meaning of this is that all theorems from this point forward a priori only hold for a morphism with simple singular spectrum. Theorem 2.3 is an extra incantation which mystically causes these results to hold on all of

For the remainder of the lecture, fix a rank morphism with simple singular spectrum Let be its uniquely determined left singular lines, and let be the corresponding right singular lines.

Let us describe the polar decomposition of , which is an almost automatic consequence of the upstairs SVD of ,

where and is the orthogonal projection of onto the left singular line

Proposition 21.4. (Left polar decomposition) We have

is the operator

and is the partial isometry

Proof: Because the left singular lines of are pairwise orthogonal, the projections satisfy

where is the identity operator. We thus have

as claimed.

Problem 21.2. Prove that is a partial isometry if and only if all its singular values are equal to

As the name “left polar decomposition” suggests, every also admits a right polar decomposition. This is obtained by observing that each of the rank one partial isometries in the upstairs SVD of can be written as

where is the orthogonal projection of onto the right singular line

Proposition 21.3. (Right polar decomposition) We have

where is as in Proposition 21.2 and is the operator

Proof: Because the right singular lines of are pairwise orthogonal, we have

Thus,

as claimed.

Now we come to the geometric definition of the adjoint, which relies on uniqueness of the SVD.

Definition 21.4. The adjoint of is the morphism defined by the conditions:

1. The left singular lines of are the right singular lines of ;
2. The right singular lines of are the left singular lines of ;
3. The singular values of coincide with the singular values of

As automatic consequences of the definition, we have that

Equivalently, Definition 21.4 says the following: given the “upstairs” SVD of

we define to be the morphism whose upstairs SVD is

From here, we see that the left polar decomposition of is

where is the morphism

and is the morphism

The right singular decomposition of is

where as is once again the SV-weighted sum of orthogonal projections onto the left singular lines of , which are the right singular lines of

Problem 21.3. Show that the operators and are given by weighted projection sums

The rest of the course (and virtually all of Math 202B) is about the Hilbert space of endomorphisms of an underlying Hilbert space . The reason for this is that is an algebra: in addition to scalar multiplication (Frobenius), it carries a notion of vector multiplication (composition), and this additional structure is the core content of Math 202B. But even ignoring this additional structure for the moment and simply thinking of as a special case of in which and happen to coincide, there are interesting things to be said wrt SVD.

Definition 21.6. An operator is said to be normal if its left and right singular lines coincide.

Perhaps you know that this is not the normal definition of normal – if so, forget that corrupt knowledge and accept in its place the geometric truth that is Definition 21.1.

Problem 21.4. Show that every normal operator commutes with its adjoint,

Let be any two finite-dimensional Hilbert spaces, and let be an arbitrary morphism.

Theorem 19.1 (Geometric SVD) We have orthogonal decompositions

where is the rank of , the spaces are lines, the numbers are positive, and the restrictions are of the form with an isometric isomorphism for

In this theorem, “decomposition” really means two things: first, it refers to simultaneous orthogonal decompositions of the spaces and into orthogonal lines with chunky remainders and and second it refers to a corresponding decomposition of the transformation into a combination of line-to-line mappings and a terminal collapsing of the (possibly non-existent) chunk into the zero vector of The decomposition of may be written compactly as

where is the orthogonal projection of onto the subspace The best way to consider this operator decomposition is an orthogonal decomposition of in a Hilbert space of transformations, which makes the singular values the coordinates of .

More precisely, is itself a Hilbert space: letting and be orthonormal bases, we defined the Frobenius scalar product on by

,

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 and used to construct it. Equivalently, if and are unitary operators then the Frobenius scalar product satisfies

Now let us consider Theorem 19.1 from the point of view of Hilbert space geometry in equipped with the Frobenius scalar product. Let us write the SVD of as

,

where

Proposition 19.2. is an orthonormal set in

Proof: Let be an ordered orthonormal basis adapted to the decomposition and let be an ordered orthonormal basis adapted to the decomposition This means that, for each we have

Equivalently, the transformation which acts on by first orthogonally projecting onto and then mapping this line isometrically onto the line is a rank one isometry.

Now compute the Frobenius norm of using the adapted basis

Similarly, suppose and consider the scalar product

There are two mutually exclusive cases for the term in this sum corresponding to a given First case: lies on neither of the lines , so is the zero vector in Second case: lies on at least one of the lines so at least one of the vectors is the zero vector in

Now, the rank of satisfies but we can extend the orthonormal set to an orthonormal basis, relative to the Frobenius scalar product. Then, the SVD simply says that the singular values of are its nonzero coordinates in this basis. In particular, we have the following

Proposition 19.3. For any we have

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 of two morphisms are are determined by the singular values of the summands and . More conceptually, this means that we want to define functionals on which send a morphism to its th largest singular value (so there are of these functionals). These functionals are nonlinear and it is difficult to say much about them in general. One thing we can say immediately is that

which is a consequence of the fact that is the operator norm of and indeed most statements that can be made are inequalities rather than identities. However, the following identity is an immediate consequence of the Hilbert space structure on

Proposition 19.4. For any we have

Proof: By Proposition 19.2, this is an instance of the Parallelogram Law.

***Happy Thanksgiving – all problems here due 12/03, 23:59.***

In Lecture 19, we interpreted the SVD of a morphism in terms of the Hilbert space geometry of equipped with the Frobenius scalar product. Let us start “downstairs,” with the orthogonal decompositions

The left singular lines are orthogonal one-dimensional subspaces of and the right singular lines are orthogonal one-dimensional subspaces in The restriction of to for has the form with a line-to-line isometry and Corresponding to this, we have an “upstairs” decomposition

happening in the Hilbert space , where and is the orthogonal projection of onto the line In Lecture 19, we proved that is an orthonormal set wrt the Frobenius scalar product, hence it can be extended to an orthonormal basis of the Hilbert space such that

Thus, for any the vector defined by

has coordinates

and is simply the orthogonal projection of the vector onto the coordinate space Remembering that are morphism and not just inert vectors, we ask: what is the significance of as a linear transformation from into ?

Theorem (Eckart-Young-Mirsky): Among all rank morphisms in the transformation is an optimal approximation to More precisely, if is any morphism of rank , then in Frobenius norm.

At a recent conference, my colleague Jorge Garza-Vargas emphasized to me that this result is crucial in applications of linear algebra to data compression, and that I would be doing you the student a grave injustice if I skipped it. So we will now prove the EYM theorem via a geometric argument which hopefully gives some understanding of why this result matters in data compression.

First of all, the upstairs SVD of is by construction

so it is clear that the rank of is indeed Our task is to demonstrate that if is an arbitrary transformation of rank then

We will decompose this into a two-part optimization problem by first optimizing over all approximants with a fixed image, and then optimizing over the image. Thus, let be a point in the Grassmannian of -dimensional subspaces of

Problem 20.1. Show that the optimization problem

is solved by where is the orthogonal projection of onto the subspace

The morphism is called the compression of into and by construction it has rank It remains now to optimize the functional

over To do this we will express in terms of the singular data of . Let and be ordered orthonormal bases adapted to the downstairs decompositions

This means that and are orthonormal bases of and such that

for which is summarized by saying that are left singular vectors for and are right singular vectors for . The remaining vectors in form an orthonormal basis of the kernel of in , while the remaining vectors in form an orthonormal basis for the complement of the image of in Now, to any subspace we associate the compression numbers defined as the norms

of the vectors obtained by projecting each right singular vector of onto Note that is in fact independent of which unit vector we sample from the line since any other unit sample from will be a scalar multiple of by a complex number of modulus one. Note that 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 -dimensional subspace.

Problem 20.2. Show that for any we have

Now we are ready to quantify compression error.

Problem 20.3. Show that

Let us write the error formula above as

Here we are seeing that the squared error in approximating by the compression is at most the Frobenius norm of which is the error we incur if we compress to zero.

Our task now is to maximize the part of the sum which reduces this worst-case error. This is a very simple optimization problem: maximize the quadratic form

subject to the constraints

Remembering that the coefficients of satisfy

our optimal strategy is to put as much weight as possible on the largest coefficients by taking

Problem 20.4. Finish the proof of the EYM theorem by showing that the compression numbers of realize the above maximizer, and that the corresponding compression is

Today – a virtual field trip to the Simons Institute for the Theory of Computing, more specifically to the workshop “Randomness, Invariants, and Complexity in Linear Algebra.”