In preparation for this, my last blog entry, I worked out ahead of time a number of possible topics regarding singular value decomposition that would be both interesting and informative. I considered everything from data compression to signal noise reduction, but evidently failed to consider that all these topics would have been covered in some form or another by my classmates before I get around to researching my own post. So, after putting my fate in the hands of Google and Wikipedia, a present you with a slightly yet obvious, but hopefully still interesting, application of the singular value decomposition: graph partitioning!

The problem: suppose you have a graph G = (V, E). Find an edge cut C that divides V into A and A’ = G - A, such that the ratio of |C| to the minimum of |A| and |A’| is as small as possible. Qualitatively speaking, this will generally result in two sets of roughly equal size (since one being significantly smaller than the other will result in a larger ration), that are connected by very few edges. Finding an exact solution for this problem is non-trivial, but a heuristic method using singular vectors can guarantee a ration no greater than sqrt(2*optimal).

Without going into all the details behind the theory, which involves the slicing of hyper-dimensional euclidean spaces, we let A = the edge incidence matrix of G. If edge j has endpoint i, then A[i, j] = 1, else A[i, j] = 0. Now that we have an A, of course, there’s only one thing to do. Calculate the SVD (or let Matlab calculate the SVD; either way…)!

As you know the SVD will give you a product A = U∑V*, where the columns of U consists of left singular vectors for each respective singular value σ. Take the second such vector u = [u1, u2, …, un]. From here one must simply iterate over ever uj, cutting the graph into two sets of vertices such that vertex i is in A if and only if qi <= qj. Of these n partitions, we pick that with the lowest ratio.

As stated above, the precise reason for why this works isn’t explained easily. For the purpose of this overview, we can simply say that matrix A is equivalent to an embedding of points in a |E| dimensional space such that adjacent vertices are necessarily located closer together than those which are not. The selection of each uj in the second singular vector corresponds to a hyper-planer partition of this set.

The point of all this, however, is that the applications of matrix factorizations include more than just image processing, or other problems that can be trivially represented as matrices. Continuing with the theme of graph algorithms, a similar technique using the smallest singular vector might be used to solve coloring problems.

For more information on SVD applications or graph partitioning, I provide the following links:

Clustering large graphs
Bipartite graphs and data clustering
Graph Partitioning
Some uses of spectral methods