Monthly Archives: February 2012

Lecture 15: Low-rank approximation of matrices

1. Low-rank approximation of matrices Let be an arbitrary matrix. We assume . We consider the problem of approximating by a low-rank matrix. For example, we could seek to find a rank matrix minimizing . It is known that a … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 14: Spectral sparsifiers

1. Spectral Sparsifiers 1.1. Graph Laplacians Let be an unweighted graph. For notational simplicity, we will think of the vertex set as . Let be the th standard basis vector, meaning that has a in the th coordinate and s … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 13: The Ahlswede-Winter Inequality

1. Useful versions of the Ahlswede-Winter Inequality Theorem 1 Let be a random, symmetric, positive semi-definite matrix such that . Suppose for some fixed scalar . Let be independent copies of (i.e., independently sampled matrices with the same distribution as … Continue reading

Posted in Uncategorized | 1 Comment

Lecture 12: Concentration for sums of random matrices

1. Concentration for sums of random matrices Let be a random real matrix of size . In other words, we have some probability distribution on the space of all matrices, and we let be a matrix obtained by sampling from … Continue reading

Posted in Uncategorized | Leave a comment

Notes on Symmetric Matrices

1. Symmetric Matrices We review some basic results concerning symmetric matrices. All matrices that we discuss are over the real numbers. Let be a real, symmetric matrix of size and let denote the identity matrix. Perhaps the most important and … Continue reading

Posted in Uncategorized | 3 Comments

Lecture 11: Graph Sparsifiers

1. Graph Sparsifiers Let be an undirected graph. How well can be approximated by a sparse graph? Such questions have been studied for various notions of approximation. Today we will look at approximating the cuts of the graph. As before, … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 10: Minimum Cuts by the Contraction Algorithm

In the first lecture we discussed the Max Cut problem, which is NP-complete, and we presented a very simple algorithm that gives a approximation. Today we will discuss the Min Cut problem, which is in P, and we will present … Continue reading

Posted in Uncategorized | Leave a comment