4 ms·

Lecture Notes on Randomized Linear Algebra (2013)

163 points by iamaaditya 10y ago

rajasinghe 10y ago
This stuff is incredibly useful when dealing with large matrices. The idea is that an n-by-n matrix often doesn't contain n^2 pieces of independent information, but can be written a product of matrices of size at most n-by-r (for r << n). A famous example of this is the Netflix recommendation matrix. In this case, you can often avoid O(n^2) complexity by only dealing with such low-rank approximations. It should be noted that this overview dates from 2013 and that a lot of new results have appeared since then. The author gives some good references in the abstract.
- apathy 10y ago
  Sparse x low-rank: if you collected every cell in the matrix, you paid too much for your sensor :-) Emmanuel Candes' lectures on compressed sensing changed my life.
- sytelus 10y ago
  Is this a more formal treatment for algorithm that Simon Funk gave? http://sifter.org/~simon/journal/20061211.html http://sifter.org/~simon/journal/20061211.html
  - jey 10y ago
    That's more related to 'stochastic gradient descent' for 'matrix completion'. The key difference is that Simon Funk's algorithm doesn't treat missing entries as a zero, whereas using linear algebra based techniques on the observed data matrix (formed by putting zeros for unobserved entries) would try to predict the missing entries as zero exactly. Also related is the 'alternating least squares' algorithm.
- dang 10y ago
  Great comment! We put 2013 in the title above.
shas3 10y ago
This is a very good and timely compilation of all the important topics! I ask this earnest question because I have a deep interest in randomized linear algebra, random projections, 'sketching'/sampling, compressive sensing, etc.: Do any of you use it in industry applications? If so, at a high level, how do you use it? I know I'm asking a "I have a hammer and that is a nail"-type question, but I am interested in seeing "deployable" applications of these topics. I don't have any to report, other than academic ones.
- sshekh 10y ago
  Compressive Sensing is widely used in imaging. https://en.wikipedia.org/wiki/Compressed_sensing#Applications https://en.wikipedia.org/wiki/Compressed_sensing#Application...
  - lp251 10y ago
    Not a great example. Compressive imaging is (was?) a hot research area but hasn't made the transition to industry. I can think of only a single commercial product that relies on compressive sensing.
    - JustFinishedBSG 10y ago
      Don't most lossy codecs make use of compressed sensing?
      - lp251 10y ago
        It's tricky. You need to define what "compressed sensing" is. Of course, for 10 years, anything with a hint of sparsity has had the "compressed sensing" buzzword added, even though these ideas are decades old. Many lossy codecs utilize the fact that the signals of interest (audio, video, images, whatever) are sparse when viewed in some transform domain- Fourier or wavelet. We apply the transformation and retain only the largest coefficents- these get quantized and transmitted, and then we use the inverse transformation to reconstruct our signal. The 'loss' comes from the thresholding/quantization procedure. It's certainly sparsity driven, but I wouldn't call it "compressed sensing". "Compressed sensing" should mean "stable reconstruction of my signal using data that is acquired at an optimal rate". The "optimal rate" is roughly proportional to the sparsity of the signal. Check out the first section of [1]. [1] http://vhosts.eecs.umich.edu/ssp2012//bresler.pdf http://vhosts.eecs.umich.edu/ssp2012//bresler.pdf
jey 10y ago
Related but different: Foundations of Data Science by Avrim Blum, John Hopcroft and Ravindran Kannan: https://www.cs.cornell.edu/jeh/book2016June9.pdf https://www.cs.cornell.edu/jeh/book2016June9.pdf
- putin 10y ago
  Do you know what the prereqs are for high dimensional geometry? Any additional resources? From the looks of it, the subject seems to require the knowledge of some measure theory and functional analysis. Advanced undergrad/grad level math subjects. Threshold for entry here seems very steep (at least for high-dim geo).
  - ianai 10y ago
    I'd say it's about a minor in mathematics and one or two semesters of very directed study.

163 points by iamaaditya 10y ago

This stuff is incredibly useful when dealing with large matrices. The idea is that an n-by-n matrix often doesn't contain n^2 pieces of independent information, but can be written a product of matrices of size at most n-by-r (for r << n). A famous example of this is the Netflix recommendation matrix. In this case, you can often avoid O(n^2) complexity by only dealing with such low-rank approximations. It should be noted that this overview dates from 2013 and that a lot of new results have appeared since then. The author gives some good references in the abstract.

apathy 10y ago
Sparse x low-rank: if you collected every cell in the matrix, you paid too much for your sensor :-) Emmanuel Candes' lectures on compressed sensing changed my life.
sytelus 10y ago
Is this a more formal treatment for algorithm that Simon Funk gave? http://sifter.org/~simon/journal/20061211.html http://sifter.org/~simon/journal/20061211.html
- jey 10y ago
  That's more related to 'stochastic gradient descent' for 'matrix completion'. The key difference is that Simon Funk's algorithm doesn't treat missing entries as a zero, whereas using linear algebra based techniques on the observed data matrix (formed by putting zeros for unobserved entries) would try to predict the missing entries as zero exactly. Also related is the 'alternating least squares' algorithm.
dang 10y ago
Great comment! We put 2013 in the title above.

shas3 10y ago

This is a very good and timely compilation of all the important topics! I ask this earnest question because I have a deep interest in randomized linear algebra, random projections, 'sketching'/sampling, compressive sensing, etc.: Do any of you use it in industry applications? If so, at a high level, how do you use it? I know I'm asking a "I have a hammer and that is a nail"-type question, but I am interested in seeing "deployable" applications of these topics. I don't have any to report, other than academic ones.

sshekh 10y ago
Compressive Sensing is widely used in imaging. https://en.wikipedia.org/wiki/Compressed_sensing#Applications https://en.wikipedia.org/wiki/Compressed_sensing#Application...
- lp251 10y ago
  Not a great example. Compressive imaging is (was?) a hot research area but hasn't made the transition to industry. I can think of only a single commercial product that relies on compressive sensing.
  - JustFinishedBSG 10y ago
    Don't most lossy codecs make use of compressed sensing?
    - lp251 10y ago
      It's tricky. You need to define what "compressed sensing" is. Of course, for 10 years, anything with a hint of sparsity has had the "compressed sensing" buzzword added, even though these ideas are decades old. Many lossy codecs utilize the fact that the signals of interest (audio, video, images, whatever) are sparse when viewed in some transform domain- Fourier or wavelet. We apply the transformation and retain only the largest coefficents- these get quantized and transmitted, and then we use the inverse transformation to reconstruct our signal. The 'loss' comes from the thresholding/quantization procedure. It's certainly sparsity driven, but I wouldn't call it "compressed sensing". "Compressed sensing" should mean "stable reconstruction of my signal using data that is acquired at an optimal rate". The "optimal rate" is roughly proportional to the sparsity of the signal. Check out the first section of [1]. [1] http://vhosts.eecs.umich.edu/ssp2012//bresler.pdf http://vhosts.eecs.umich.edu/ssp2012//bresler.pdf

jey 10y ago

Related but different: Foundations of Data Science by Avrim Blum, John Hopcroft and Ravindran Kannan: https://www.cs.cornell.edu/jeh/book2016June9.pdf https://www.cs.cornell.edu/jeh/book2016June9.pdf

putin 10y ago
Do you know what the prereqs are for high dimensional geometry? Any additional resources? From the looks of it, the subject seems to require the knowledge of some measure theory and functional analysis. Advanced undergrad/grad level math subjects. Threshold for entry here seems very steep (at least for high-dim geo).
- ianai 10y ago
  I'd say it's about a minor in mathematics and one or two semesters of very directed study.