Hacker News Reader

Comment by ivansavz | Hacker News Reader

Yeah. I don't know why LA courses focus so much on eigenvalues, and don't talk much about SVD. It seems like an obvious next step once you know how to compute eigenvalues, but SVDs are always covered in passing and superficially (at least in courses I've taken).

I find it fascinating that A = U∑V^T works on ANY matrix A, with U and V being made of orthogonal vectors (the left and right singular vectors of A)... it's like saying that all matrices are scalings and projections when viewed with appropriate bases for the input and output spaces (U and V).

> we can find the left and right singular values

Interestingly the (nonzero subset) of the left and right singular values happen to be the same... I don't have a useful intuition about how to explain this. Does anyone know why A A^T and A^T A have the same eigenvalues?

View on HN

> Yeah. I don't know why LA courses focus so much on eigenvalues, and don't talk much about SVD.

It makes sense to talk about the eigenvalues of an operator on any vector space. But in order for singular values to make sense the vector space needs to have an inner product.

So eigenvalues are more general because they make sense even when you haven't chosen an inner product on your vector space.

From an HN perspective this kind of consideration is relevant when working on a data set in which there are some arbitrary units. You don't want your model predicting house prices to work differently depending on whether you choose to measure floor size in m^2 or ft^2.

Could you elaborate on why SVD requires an inner product structure (choice of scale) while eigenvalues do not? Do you just mean that the input and output vector spaces might generically have different units, and so one would need to use some sensible "normalized" units?

There's probably more than one perspective on this. Here's one: a standard way to approach SVD is to start with a matrix A and consider A^TA and AA^T. Since the latter is symmetric (or hermitian if on a complex vector space, where transpose is replaced by adjoint), by the spectral theorem it has real eigenvalues and orthonormal eigenvectors, from which the SVD can be deduced.

But the definition of A^T or A^* depends on a particular choice of basis, and is not a coordinate-invariant concept. If one had an inner product <,>, the adjoint can be defined in a coordinate-independent way using that inner product: A^* is the operator defined by

<Au,v> = <u,A^v>

for all vectors u and v. (One can check that A^ is uniquely defined.) For a different choice of inner product, one gets a different A^.

Note that the operator A^TA comes up naturally when one considers what the action of A does to the length of vectors:

|u|^2 = <u,u>

|Au|^2 = <Au,Au> = <u,A^Au>

Geometrically, the SVD tells us how a linear transformation dilates or contracts space in different directions, e.g., think about what a linear transformation does to a sphere. But all these concepts -- length of vectors, spheres, ellipsoids (images of spheres under linear transformations) -- depend on a choice of inner product.

Singular values of a transform are defined using the "operator norm" of the transform.

The norm is defined in terms of the inner product.

On the other hand, eigenvalues are defined with using only the transform and scalar multiplication, which does not require an inner product.

I'm not sure you need to do that (define singular values via the operator norm), but one thing I don't see a solution for is getting rid of the requirement of the inner product for the definition of the adjoint.

The SVD breaks a linear transformation into 3 parts:

(1) A rotation in the source space, (2) an axis-aligned non-uniform scaling (if necessary adding/removing dimensions to match the destination space), and (3) another rotation in the destination space.

Rotation is only a meaningful concept when you have a metrical structure (think of the full geometry of Euclid’s Elements including circles, perpendicularity, lengths, angles), so if you don’t have a metrical structure the SVD is likewise not really meaningful.

Often spaces we deal with using linear algebra only have an affine structure (parallelism is well defined, and lengths can be compared when they are along parallel lines), but do not have a metrical structure (so there is no meaningful way to compare lengths pointed in different directions or measure angles). For example: there is no meaningful concept of the angle between the directions of 5 miles/gallon and 10 miles/gallon, and if you arbitrarily defined one, it would change when you switched from gallons to milliliters or from miles to meters.

In practice people still often arbitrarily impose a metrical structure, sometimes based on some heuristic analysis of the data involved, and then use tools like the SVD based on that.

The really short answer is that (one off) the definition(s) of SVDs uses the transpose, which requires a inner product.

Any two matrices AB and BA have same eigen values. Say v is an eigen vector of AB with eigen value lambda : you have ABv = lambda v. Now BA(Bv) = B(ABv) = B(lambda v) = lambda*(Bv). So, Bv is an eigen vector of BA with eigen value lambda.

Trefethen and Bau's Numerical Linear Algebra (http://people.maths.ox.ac.uk/trefethen/text.html) introduces SVD up-front, before discussing how to compute anything.

SVDs are the entry point to topic models, e.g. NNMF. Super interesting and useful for modeling large datasets efficiently.

Reply on news.ycombinator.com