Great video! I want to add a couple of references to what you mentioned in the video related to neural networks: 1. Ali Rahimi got the Neurips 2017 "test of time" award for a method called - Random kitchen sinks (kernel method with random features). 2. Choromansky (from Google) made a variation of this idea to alleviate the quadratic memory cost of self-attention in transformers (which also works like a charm - I tried it myself, and I'm still perplexed how it didn't become one of the main efficiency improvements for transformers.). Check "retrinking attention with performers". Thank you for the great work on the video - keep them coming please! :)
it didn't because all efficient variations have significantly worse performance on retrieval tasks (associative recall for example), as all recent papers demonstrated
@@howuhh8960 do you have specific references for this claim? I'm not doubting you, I'm just really interested in learning more, and the literature is vast.
As a mathematician specializing in probability and random processes, I approve this message. N thumbs up where N ranges between 2.01 and 1.99 with 99% confidence!
As a developer at AMD I feel somewhat obligated to note we have an equivalent to cuBLAS called rocBLAS, as well as an interface layer hipBLAS designed to compile code to make use of either AMD or NVIDIA GPUs.
Another tidbit about LinPack: One of its major strengths at the time it was written was that all of its double precision algorithms were truly double precision. At that time other packages often had double precision calculations hidden within the single precision routines where as their double precision counter parts did not have quad-precision parts anywhere inside. The LinPack folks were extraordinarily concerned about numerical precision in all routines. It was a great package. It also provided the basis for Matlab
And it's so good at using CPU resources as optimally as possible that Intel used it for stress and stability testing their CPUs for years (and still do to some degree AFAIK)
Brunton, Kutz et al. in the paper you mentioned here "Randomized Matrix Decompositions using R," recommended in their paper using Nathan Halko's algo, developed at the CU Math department. B&K give some timing data, but the time and memory complexity were already computed by Halko, and he had implemented it in MATLAB for his paper - B&K ported it to R. Halko's paper from 2009 "FINDING STRUCTURE WITH RANDOMNESS: STOCHASTIC ALGORITHMS FOR CONSTRUCTING APPROXIMATE MATRIX DECOMPOSITIONS" laid this all out 7 years before the first draft of the B&K paper you referenced. Halko's office was a mile down the road from me at that time, and I implemented Python and R code based on his work (it was used in medical products, and my employer didn't let us publish). It does work quite well.
Very cool! The more I researched this, the more I realized the subject was deeper (older too) than I had realized with the first few papers I read. It's interest to hear your on-the-ground experience of it, and I'm glad the video got your attention.
@@Mutual_Information Has anyone tried genetic algorithms instead of purely random approches? In my experience, genetic algorithms are 100 faster than Monte Carlo simulations to obtain an optimum.
I'm finally far enough in education to see how well made your stuff is. Super excited to see a new one from you. Thanks for expanding people's horizons!
I have seen a very similar idea in compressed sensing. In compressed sensing we also use a randomized sampling matrix, because the errors can be considered as white noise. We can then use a denoising algorithm to recover the original data. In fact I know Philips MRI machines use this technique to speed up scans, because you have to take less pictures. Fascinating
Compressed sensing is also useful for wireless comunications. I studied its usage for sampling ultra wideband signals and indoor positioning. It only works accurately under certain sparsity assumptions. In MRI scans , their "fourier transform" can be considered sparse, then we can use l1 denoising algorithms to recover the original signal.
@@MrLonelyrager yes correct, that's exactly what I used. In the form of ISTA (iterative shrinkage and thresholding) algorithms and its many (deep-learning) derivatives
You discussed all the priors incredibly well. I didn’t even understand the premise of random in this context and now I leave with a lot more. Keep it up man ur videos are the bomb
It feels like this video was made to match my exact interests LOL I've been interested in NLA for a while now, and I've recently studied more "traditional" randomized algorithms in uni for combinatorial tasks (e.g. Karger's Min-cut). It's interesting to see how they've recently made ways to combine the 2 paradigms. I'm excited to see where this field goes. Thanks for the video and for introducing me to the topic!
Another neat explanation for why the randomized least-squares problem works is the Johnson-Lindenstrauss lemma. That lemma states that most vectors don't change length a lot when you multiply them by a random gaussian matrix, so the norm of S(Ax - b) is within (1-eps) to (1+eps) of the norm of Ax-b with high probability.
I used one time random matrices for eigenvalue counts on intervals and it was amazing! Di Napoli, E., Polizzi, E., & Saad, Y. (2016). Efficient estimation of eigenvalue counts in an interval. Numerical Linear Algebra with Applications, 23(4), 674-692.
I realize that YT comments are not the best place to explain "complex" ideas, but here it goes anyway: The head bending relative difference piece reply is "just" a coordinate transformation. At 29:45, you lay ellipses atop each other and show the absolute approximation difference between the full sample and the sketch. The "trick" is to realize that this happens in the common (base) coordinate system and that nothing stops you from changing this coordinate system. For example, you can (a) move the origin to the centroid of the sketch, (b) rotate so that X and Y align with the semi-axis of the sketch, and (c) scale (asymmetrically) so that the sketches semi-axis have length 1. What happens to the ellipsoid of the full sample in this "sketch space"? Two things happen when plotting in the new coordinate system: (1) the ellipsoid of the sketch becomes a circle around the origin (semi-axes are all 1) by construction. (2) the ellipsoid of the full sample becomes an "almost" circle depending on the quality of the approximation of the full sample by the sketch. As sample size increases, centroids converges, semi-axes start aligning, and (importantly) semi-axes get stretched/squashed until they reach length 1. Again, this is for the full sample - the sketch is already "a perfect circle by construction". In other words, as we increase the sample size of the sketch the full sample looks more and more like a unit circle in "sketch space". We can now quantify the quality of the approximation using the ratio of the full sample's semi-axis in "sketch space". If there are no relative errors (perfect approximation), these become the ratio of radii of a circle which is always 1. Any other number is due to (relative) approximation error, lower is better, and it can't be less than 1. The claim now is that, even for small samples, this ratio is already low enough for practical use, i.e., sketches with just 10 points already yield good results.
If you understand the above, then the high-dimensional part becomes clear as well: In N dimensions a "hyper-ellipsoid" has N semi-axes, and the claim is that for real (aka. sparse) problems some of these semi-axes are really large and some are really small when measured in "problem space". This relationship applied to the 2D ellipsis you show at 29:45 means that the primary axis becomes really large (stretches beyond the screen size) and the secondary axis becomes really small (squished until the border lines touch each other due to line thickness). This will make the ellipsis plot "degenerate" and it will look like a line - which is boring to visualize.
This was a nice walk down memory lane for me, and a good introduction to the beginner. It's nice to see SWE getting interested in these techniques, which have a very long history (like solving finite elements with diffusion decades ago, and compressed sensing). I enjoyed your video. A few notes: It's useful to note that "random" projections started out as Gaussian, but it turns out very simple, in-memory, transformations let you use binary random numbers at high speed with little to no loss of accuracy. I think you had this in mind when talking about the random matrix S in sketch-and-solve. BLAS sounds like blast, but without the t. I'm sure there's people who pronounce it like blahs. Software engineers mangle the pronunciation of everything, including other SWE packages, looking at you, Ubuntu users. However the first pronunciation is the pronunciation I have always heard in the applied linear algebra field. FORTRAN doesn't end like "fortune," but rather ends with "tran," but maybe people pronounce "fortran" (uncapitalized) that way these days - IDK (see note above re: mangling; FORTRAN has been decapitalized since I started working with it). Cholesky starts with a hard "K" sound, which is the only pronunciation you'll ever hear in NLA and linear algebra. It certainly is the way Cholesky pronounced it. Me, I always pronounce Numpy to sound like lumpy just to tweak people, even though I know better ☺. I've always pronounced CQRRPT as "corrupt," too, but because that's what the acronym looks like (my eyes are bad). One way to explain how these work intuitively is to look at a PCA, similar to what you touched on with the illustration of covariance. If you know the rank is low, then there will be, say, k large PCA directions, and the rest will be small. If you perform random projection on the data, those large directions will almost certainly show up in your projections, with the remaining PCA directions certainly being no bigger than they were originally (projection is always non-expanding). This means the random projections will still contain large components of the strong PCA directions, and you only need to make sure you took enough random projections to avoid being unlucky enough to accidentally be very nearly normal with the strong PCA directions every time. The odds of you being unlucky go down with every random projection you add. You'd have to be very unlucky to take a photo of a stick from random directions, and have every photo of the stick be taken end-on. In most photos, it will look like a stick, not a point. Similarly, taking a photo of a piece of paper from random directions will look like a distorted rectangle, not a line segment It's one case where the curse of dimensionality is actually working in your favor - several random projections almost guarantees they won't all be projections to an object that's the thickness of the paper. I've been writing randomized algos for a long time (I have had arguments w engineers about how random SVD couldn't possibly work!), and love seeing random linear algebra libraries that are open and unit tested. I agree with your summary - a good algorithm is worth far more than good hardware. Looking forward to you tracking new developments in the future.
This is the real test of a video. When an expert watches it and, with some small corrections, agrees that it gets the bulk of the message right. It's a reason I try to roll in an subject matter expert where I can. So I'm quite happy to have covered the topic appropriately in your view. (It's also a relief!) And I also wish I had thought of the analogy: "You'd have to be very unlucky to take a photo of a stick from random directions, and have every photo of the stick be taken end-on. In most photos, it will look like a stick, not a point." I would have included that if I had thought of it!
3:03 Linear algebra professor, here. Please stop teaching that it's the rows of matrices which are vectors. Yes, both rows and columns of matrices correspond to vectors in separate vector spaces, but when they don't have the full picture yet, beginning students should be thinking of the columns of the matrix as 'the' vectors. I've had to spend so much work fixing the perspective of engineers in their masters program who only think of the rows as vectors. It's much easier to broaden a student's perspective from columns to also rows, than it is to broaden their perspective from rows to also columns.
Thanks for sharing this perspective! I've heard something similar from a professor when I did my PhD, and I generally agree with it. That said, I think introducing row-wise is not so bad *in the specific context of this video.* It seems like the natural thing to do if we want to compare scalar-valued nonlinear functions to scalar-valued linear functions. So if you're in a time crunch and you need to explain the concept of linearity in one minute (and with few equations), then this approach seems not so bad.
You are an amazing teacher! Thank you for explaining the topic in this manner. It really motivates me to continue learning about all things linear algebra!
The nice thing is, with continuous systems (and everything in experienced life is continuous) the question is not "is it linear," but "on what scale is it functionally linear," which makes calculations of highly complex situations much simpler.
That is an excellent example as to why engineering uses approximations - we can closely model on a given scale any system using known functions. I did not know about that function before though, that's super interesting!
Bravo! ! As an LA math teacher and Linear Algebra student in college, you confirmed why children need to learn Algebra-1 with the infamous Quadratic formula to understand how Linear Algebra works and is necessary to understand A.I. Please do more Linear Algebra videos for high school and college students and other interested lay people. Many Thanks.
you've GOT to post more, this stuff is amazing, im still in high school but learning about so-called 'mature' processes which become completely revolutionised really inspires me, thanks for this :)
As hobbyist mathematician, please, don’t say that f(x) is a function or worse : a linear function. f(x) is a number in most cases you described. f on the other hand is a function and f can be linear
f(x) can be a matrix or even a function (that is what we call in computer programming higher order function) but I don’t think that was the intended message
Masterful explaination, going through the math and providing high-level abstractions of concepts. Really helps seeing how someone could invent a major discovery.thanks
Oh my god, this forms a small part of my PhD thesis where I've been trying to understand LAPACK's advantage/disadvantage when it comes to inverting matrices. Having this video really helps me put things into contex! Thank you very much for making this!
Great and clear video! Makes me wanna study more numerical LA...combined with probability theory because it shows how likely inefficient many algorithms use currently are, and that randomized algorithms are usually insanely much faster, while being approximately correct. So those randomized algorithms basically can be used anywhere when we don't need to be 100% sure about the result (which is basically always, because our mathematical models are only approximations of what's going on in the world and thus are inaccurate anyways and as you mentioned, if data is used, it's noisy).
Yep, otherwise the linearity of addition and multiplication which he just skipped over wouldn't apply and thus wouldn't be linear functions, or rather the correct term is linear map/transformation. Example: F(x,y,z) = (2x+y, 3y, z+5), (0,0,0) = F(0,0,0) is incorrect because F(0,0,0) = (0,0,5). The intent is to preserve the linearity of these operations so they can be applied similarly. If I want 2+2 or 2*2 I can't have 5
Excellent video! This topic is not easy for the layperson (admittedly, the layperson that likes Linear Algebra), but it was clearly and very well structured.
Great video ! I had a compressive sensing class this semester, it sure is a very interesting and promissing topic of reasearch ! But I'm not sure that video games would benefit a lot from it ? If I understood correctly, the gains are mostly at high dimension, while video games linear algebra is basically only 3D, do you have exemples ? Thanks again !
I've been through some basic linear algebra courses, but really the covariance problem struck me as one obviousness to a statician. A statician would never go and sample everybody, they would first determine how accurate they needed to be in their certainty, and then go about sampling exactly the number of people that satisfies that equation. I actually had to do this in my job! I can totally see how this will be a great tool used with data prediction and maybe hardware accelerators to make MASSIVE gains. We are in for a huge wild ride! Thanks for the video!
Reminds me of what my high school maths teacher said about being able to assess product quality on a production line with high accuracy by only sampling a few percent of the product items.
why did i not found your channel before ! some channel steal my view time, but yours get me 10 years younger discovering a new domain :) i feel i m going to buy some books and papers again ! thank you!
I love how you explain things with no assumptions, but also don’t assume we know nothing. You let us walk in the field without getting lost in the weeds🤙
Very nice video and it's indeed a very interesting promising direction for many applications where it doesn't matter if it's not exact as long as the answer is correct to an acceptable error margin, I especially like the start with UE5 because games and especially graphics has been one area where using randomness and shortcuts to get "close enough fast enough" has always been a priority. It'd be absolutely amazing to have a RandNLA library with basically a "Speed Accuracy" slider.
I don’t know how long it took for you to create this video with fancy slides and examples, but everything is so well explained that I wish I had you as my teacher
The trick of multiplying by random S in argmin (SAx-Sb)^2 reminds me of the similar trick in the Freivalds' algorithm: instead of verifying matrix multiplication A*B==C we check A*B*x==C*x for a random vector x. Random projections FTW???
"And if you aren't, you're probably doing something wrong." So very very true. Don't roll your own NLA code. You won't get it right and it certainly won't be faster. The corollary is "If you're inverting a matrix, you're probably doing something wrong." But that's a different problem I have to solve with newbies.
The first program I fed a computer was one I wrote in FORTRAN IV. It almost exhausted the memory capacity of the IBM machine, which was about 30 KBytes for the user (it used memory overloads, which we'd call banked memory today, in order to not exceed the available memory for programs).
Some small correction: At 4:50, assuming the plotted values follow y=f(x), f is actually not linear, since in the graph we see that f(0)/=0. At 8:22, you incorrectly refer to the computer's registers as "registries", but more importantly, data access speed depends much more on cache size than register size, as the latter can generally only hold 1-4 values (32-bit float in 128-bit register), which, while allowing the use of SIMD, is very restrictive in its use. A computer's cache is some intermediate between CPU and disk, which, if used efficiently, can indeed greatly reduce runtime.
Very interesting content! I did find that the video felt longer than expected. I was intrigued by the thumbnail and the promise of at least 10x speed improvement. However, it took quite a while to get to the papers and even longer to get to the explanation. The history definitely deserves its own video and most chapters could be much shorter.
Let me try to phrase it for people who have no math degree education, but rather engineering level: You effectively select the best fitting equations of the linear problem which is originally highly overdefined for your x vector to sufficiently represent the complete system with a small subset of the original equations. - correct? That's not directly "inducing random noise" but rather a simplification by omission of probably irrelevant equations. This reminds me of how we did such a scheme for a "bundle block adjustment" application: We used the drastic performance boost from simplification to do multiple simple bba within each reaction step of the system with different drastically simplified subsets from the data, to then compare the results with the expected outcome (low rest error, good alignment with the continuation of the coordinates of our x vector from the previous step), then performing a final selection based on those outcomes and then performing a final error minimizing solving with those perfectly selected equations. That gives the best from both worlds: Speed up but without sacrificing correctness. And there is no magic at all (and no "introduced random noise"). Just a "try simple" first iteration, then based on that a selected final iteration. Basically engineering optimization based on working standard linear algebra systems.
Nearly 7 years ago when I was still a practicing geneticist, sequenced DNA would usually only be a few nucleotides long, maybe 50, and it would have to get mapped to a genome with billions of possible locations to test. The fastest algorithms ended up being used in the most published papers, so competition was pretty fierce to be the fastest. The gold standard was a deterministic program called BWA/Bowtie, but just before I left the field a new breed of non-deterministic aligners with mapping times orders of magnitude faster were developed, and it really split opinions. Different deterministic programs would give different results (i.e. they had noise/error too, even if they're consistent about it), so in many ways who cared if a program gave different results every time you ran it, particularly if you only intend to run it once... But there were other problems. You couldn't create definitive analyses anymore, you couldn't retrace someone else's steps, you couldn't rely on checksums, total nightmare. The "hidden structures" aspect of the paper was interesting, the structures are in the data, and how the algorithm interacts with the data, which as the programmer you don't have access to by definition - but you also kinda know all you need to know about it too. It feels very similar to making a good meme.
Worth pointing out that there is a modern sparse linear algebra package called GraphBLAS, that can be used not just for graphs (which generalize to sparse matrices) but also to any sparse matrix multiplication operation.
Does it mean to random sample rows from the tall matrix, with low least square errors as loss indicator (Monte Carlo method?), then to work on later stages with the newly constructed "short matrix" - such as full rank square matrix with dimension of the original columns?
I see what you're going for, and that's in the style of some of the approaches taken when the field was younger. 'row-sampling' or 'column-sampling'. The problem is, the relevant information isn't uniformly distributed (a row of all zeros isn't the same as a row with wildly different numbers). So you have to mix the information from rows or columns together, and that's what is essentially done with the matrix multiplication SA.
@@Mutual_Information Agreed. Distribution shift is the bad guy behind. But uniform sampling is the best choice as you will never know the real distribution.
Phenomenal! But I have one correction for (25:33): Full rank isn't restricted to square [invertible] matrices, it just means rank = min(m,n) rather than rank = k < min(m,n).
Do you know LightOn's OPU (Optical Processing Unit)? It can do one simple thing, multiplying with a random matrix, but it can do it lightning fast (cause it uses light). It seems like ideal hardware for this.
Great video! I want to add a couple of references to what you mentioned in the video related to neural networks:
1. Ali Rahimi got the Neurips 2017 "test of time" award for a method called - Random kitchen sinks (kernel method with random features).
2. Choromansky (from Google) made a variation of this idea to alleviate the quadratic memory cost of self-attention in transformers (which also works like a charm - I tried it myself, and I'm still perplexed how it didn't become one of the main efficiency improvements for transformers.). Check "retrinking attention with performers".
Thank you for the great work on the video - keep them coming please! :)
it didn't because all efficient variations have significantly worse performance on retrieval tasks (associative recall for example), as all recent papers demonstrated
The Quadratic Memory Cost of Self-Attention in Transformers is my new band name
Is this a similar idea compared with the latent space in the transformer?
Rahimi got the award for the "Random Features for Large-Scale Kernel Machines" paper, not the random kitchen sinks one
@@howuhh8960 do you have specific references for this claim? I'm not doubting you, I'm just really interested in learning more, and the literature is vast.
As a mathematician specializing in probability and random processes, I approve this message. N thumbs up where N ranges between 2.01 and 1.99 with 99% confidence!
Great to have you here!
So you're saying there's a 1 chance in roughly 10^16300 that you're giving him 3 thumbs up...
My brother in Christ, use a discrete probability distribution.
Only if you assume a normal distribution! @@purungo
Is this just one big late april fool's? What the hell
reminds me of that episode of veggie tales when larry was like "in the future, linear algebra will be randomly generated!"
W E E D E A T E R
Reminds you of what???
xD
I thought it would be some nice science show, but it turns out to be some kids show : (
@@rileymurray7437 he means this video: ua-cam.com/video/j4Ph02gzqmY/v-deo.htmlsi=wb2atwfoSQaefrjL
As a developer at AMD I feel somewhat obligated to note we have an equivalent to cuBLAS called rocBLAS, as well as an interface layer hipBLAS designed to compile code to make use of either AMD or NVIDIA GPUs.
but can your cards train imagenet without crashing?
@@sucimsheeeeeeeeesh
Are you guys hiring?
OP forgot about BLAS being a standard so most implementations have been forgotten, it's weird to point at Nvidia
As an AMD customer who recently bought a 6950XT for €600, I am disappointed to learn rocBLAS is not supported on my outdated 2 year old hardware.
The part about matrix multiplication reminded me of studying cache hit and miss patterns in university. Interesting video.
Dynamic programming question
Another tidbit about LinPack: One of its major strengths at the time it was written was that all of its double precision algorithms were truly double precision. At that time other packages often had double precision calculations hidden within the single precision routines where as their double precision counter parts did not have quad-precision parts anywhere inside. The LinPack folks were extraordinarily concerned about numerical precision in all routines. It was a great package.
It also provided the basis for Matlab
And it's so good at using CPU resources as optimally as possible that Intel used it for stress and stability testing their CPUs for years (and still do to some degree AFAIK)
Brunton, Kutz et al. in the paper you mentioned here "Randomized Matrix Decompositions using R," recommended in their paper using Nathan Halko's algo, developed at the CU Math department. B&K give some timing data, but the time and memory complexity were already computed by Halko, and he had implemented it in MATLAB for his paper - B&K ported it to R. Halko's paper from 2009 "FINDING STRUCTURE WITH RANDOMNESS: STOCHASTIC ALGORITHMS FOR CONSTRUCTING APPROXIMATE MATRIX DECOMPOSITIONS" laid this all out 7 years before the first draft of the B&K paper you referenced. Halko's office was a mile down the road from me at that time, and I implemented Python and R code based on his work (it was used in medical products, and my employer didn't let us publish). It does work quite well.
Very cool! The more I researched this, the more I realized the subject was deeper (older too) than I had realized with the first few papers I read. It's interest to hear your on-the-ground experience of it, and I'm glad the video got your attention.
@@Mutual_Information
Has anyone tried genetic algorithms instead of purely random approches?
In my experience, genetic algorithms are 100 faster than Monte Carlo simulations to obtain an optimum.
Halko's algorithm helped me start my understanding of Laplacian eigenmaps and other dimensionality reduction methods.
Golub and Van Loan’s textbook is goated. I loved studying and learning numerical linear algebra for the first time in undergrad.
I'm writing a paper on a related topic. Didn't know about many of these papers, thanks for sharing! I really enjoyed your video
I'm finally far enough in education to see how well made your stuff is. Super excited to see a new one from you. Thanks for expanding people's horizons!
Glad to have you watching!
I have seen a very similar idea in compressed sensing. In compressed sensing we also use a randomized sampling matrix, because the errors can be considered as white noise. We can then use a denoising algorithm to recover the original data. In fact I know Philips MRI machines use this technique to speed up scans, because you have to take less pictures. Fascinating
random sampling to reconstruct the signal
@@tamineabderrahmane248... what?
Compressed sensing is also useful for wireless comunications. I studied its usage for sampling ultra wideband signals and indoor positioning. It only works accurately under certain sparsity assumptions. In MRI scans , their "fourier transform" can be considered sparse, then we can use l1 denoising algorithms to recover the original signal.
@@MrLonelyrager yes correct, that's exactly what I used. In the form of ISTA (iterative shrinkage and thresholding) algorithms and its many (deep-learning) derivatives
You discussed all the priors incredibly well. I didn’t even understand the premise of random in this context and now I leave with a lot more.
Keep it up man ur videos are the bomb
It feels like this video was made to match my exact interests LOL
I've been interested in NLA for a while now, and I've recently studied more "traditional" randomized algorithms in uni for combinatorial tasks (e.g. Karger's Min-cut). It's interesting to see how they've recently made ways to combine the 2 paradigms. I'm excited to see where this field goes. Thanks for the video and for introducing me to the topic!
UA-cam has you in its palms. _laughs maniacally_
where do you study?
I started reading this paper when you mentioned it on Twitter, forgot it was you who I got it from and was now so happy to see a video about it!
Yes! And good to see you here mgost
Another neat explanation for why the randomized least-squares problem works is the Johnson-Lindenstrauss lemma. That lemma states that most vectors don't change length a lot when you multiply them by a random gaussian matrix, so the norm of S(Ax - b) is within (1-eps) to (1+eps) of the norm of Ax-b with high probability.
Was looking for a nerdy video to fall asleep to, but couldn’t take my eyes off the screen. Excellent presentation and very well done video!
As always this is BRILLIANT. I started following your videos since I saw the GP regression video. Great content! Thank you very much.
Damn... your videos are getting beyond excellent!
My first thought was "this is like journal club with DJ"! Great stuff - well researched and crisply delivered. More of this, if you please.
its always a pleasure to watch this channel
Dang, I absolutely love videos and articles that summarize the latest in a field of research and explain the concepts well!
Amazing explanation of a complex topic! You've got yourself a new subscriber.
Glad to have you!
I used one time random matrices for eigenvalue counts on intervals and it was amazing!
Di Napoli, E., Polizzi, E., & Saad, Y. (2016). Efficient estimation of eigenvalue counts in an interval. Numerical Linear Algebra with Applications, 23(4), 674-692.
I realize that YT comments are not the best place to explain "complex" ideas, but here it goes anyway:
The head bending relative difference piece reply is "just" a coordinate transformation. At 29:45, you lay ellipses atop each other and show the absolute approximation difference between the full sample and the sketch. The "trick" is to realize that this happens in the common (base) coordinate system and that nothing stops you from changing this coordinate system. For example, you can (a) move the origin to the centroid of the sketch, (b) rotate so that X and Y align with the semi-axis of the sketch, and (c) scale (asymmetrically) so that the sketches semi-axis have length 1. What happens to the ellipsoid of the full sample in this "sketch space"?
Two things happen when plotting in the new coordinate system: (1) the ellipsoid of the sketch becomes a circle around the origin (semi-axes are all 1) by construction. (2) the ellipsoid of the full sample becomes an "almost" circle depending on the quality of the approximation of the full sample by the sketch. As sample size increases, centroids converges, semi-axes start aligning, and (importantly) semi-axes get stretched/squashed until they reach length 1. Again, this is for the full sample - the sketch is already "a perfect circle by construction". In other words, as we increase the sample size of the sketch the full sample looks more and more like a unit circle in "sketch space".
We can now quantify the quality of the approximation using the ratio of the full sample's semi-axis in "sketch space". If there are no relative errors (perfect approximation), these become the ratio of radii of a circle which is always 1. Any other number is due to (relative) approximation error, lower is better, and it can't be less than 1. The claim now is that, even for small samples, this ratio is already low enough for practical use, i.e., sketches with just 10 points already yield good results.
If you understand the above, then the high-dimensional part becomes clear as well: In N dimensions a "hyper-ellipsoid" has N semi-axes, and the claim is that for real (aka. sparse) problems some of these semi-axes are really large and some are really small when measured in "problem space". This relationship applied to the 2D ellipsis you show at 29:45 means that the primary axis becomes really large (stretches beyond the screen size) and the secondary axis becomes really small (squished until the border lines touch each other due to line thickness). This will make the ellipsis plot "degenerate" and it will look like a line - which is boring to visualize.
Thanks for taking the time to type this, it's clear(er) to me now.
This was a nice walk down memory lane for me, and a good introduction to the beginner. It's nice to see SWE getting interested in these techniques, which have a very long history (like solving finite elements with diffusion decades ago, and compressed sensing). I enjoyed your video.
A few notes:
It's useful to note that "random" projections started out as Gaussian, but it turns out very simple, in-memory, transformations let you use binary random numbers at high speed with little to no loss of accuracy. I think you had this in mind when talking about the random matrix S in sketch-and-solve.
BLAS sounds like blast, but without the t. I'm sure there's people who pronounce it like blahs. Software engineers mangle the pronunciation of everything, including other SWE packages, looking at you, Ubuntu users. However the first pronunciation is the pronunciation I have always heard in the applied linear algebra field.
FORTRAN doesn't end like "fortune," but rather ends with "tran," but maybe people pronounce "fortran" (uncapitalized) that way these days - IDK (see note above re: mangling; FORTRAN has been decapitalized since I started working with it).
Cholesky starts with a hard "K" sound, which is the only pronunciation you'll ever hear in NLA and linear algebra. It certainly is the way Cholesky pronounced it.
Me, I always pronounce Numpy to sound like lumpy just to tweak people, even though I know better ☺. I've always pronounced CQRRPT as "corrupt," too, but because that's what the acronym looks like (my eyes are bad).
One way to explain how these work intuitively is to look at a PCA, similar to what you touched on with the illustration of covariance. If you know the rank is low, then there will be, say, k large PCA directions, and the rest will be small. If you perform random projection on the data, those large directions will almost certainly show up in your projections, with the remaining PCA directions certainly being no bigger than they were originally (projection is always non-expanding). This means the random projections will still contain large components of the strong PCA directions, and you only need to make sure you took enough random projections to avoid being unlucky enough to accidentally be very nearly normal with the strong PCA directions every time. The odds of you being unlucky go down with every random projection you add. You'd have to be very unlucky to take a photo of a stick from random directions, and have every photo of the stick be taken end-on. In most photos, it will look like a stick, not a point. Similarly, taking a photo of a piece of paper from random directions will look like a distorted rectangle, not a line segment It's one case where the curse of dimensionality is actually working in your favor - several random projections almost guarantees they won't all be projections to an object that's the thickness of the paper.
I've been writing randomized algos for a long time (I have had arguments w engineers about how random SVD couldn't possibly work!), and love seeing random linear algebra libraries that are open and unit tested.
I agree with your summary - a good algorithm is worth far more than good hardware. Looking forward to you tracking new developments in the future.
This is the real test of a video. When an expert watches it and, with some small corrections, agrees that it gets the bulk of the message right. It's a reason I try to roll in an subject matter expert where I can. So I'm quite happy to have covered the topic appropriately in your view. (It's also a relief!)
And I also wish I had thought of the analogy: "You'd have to be very unlucky to take a photo of a stick from random directions, and have every photo of the stick be taken end-on. In most photos, it will look like a stick, not a point." I would have included that if I had thought of it!
@@Mutual_Information Agree absolutely!
Jim Demmel and Jack Dongarra pronounced it "blahs" the last time I spoke with each of them. (~This morning and one month ago, respectively.) 😉
@@rileyjohnmurray7568 lol
@@rileyjohnmurray7568 I hope they perk up ☺
We need more content creators like you ❤
Thank you. These videos take awhile, so I wish I could upload more. But I'm confident I'll be doing UA-cam for a long time.
@@Mutual_Information Well ,This news made my day !
3:03 Linear algebra professor, here. Please stop teaching that it's the rows of matrices which are vectors. Yes, both rows and columns of matrices correspond to vectors in separate vector spaces, but when they don't have the full picture yet, beginning students should be thinking of the columns of the matrix as 'the' vectors. I've had to spend so much work fixing the perspective of engineers in their masters program who only think of the rows as vectors. It's much easier to broaden a student's perspective from columns to also rows, than it is to broaden their perspective from rows to also columns.
Thanks for sharing this perspective! I've heard something similar from a professor when I did my PhD, and I generally agree with it.
That said, I think introducing row-wise is not so bad *in the specific context of this video.* It seems like the natural thing to do if we want to compare scalar-valued nonlinear functions to scalar-valued linear functions. So if you're in a time crunch and you need to explain the concept of linearity in one minute (and with few equations), then this approach seems not so bad.
idk, seems like skill issue.
You are an amazing teacher! Thank you for explaining the topic in this manner. It really motivates me to continue learning about all things linear algebra!
this feels like a good presentation topic for numerical methods seminar
Very good video on a very interesting topic. Who would have thought that there is this much to gain in such a commonly used piece of mathematics.
The nice thing is, with continuous systems (and everything in experienced life is continuous) the question is not "is it linear," but "on what scale is it functionally linear," which makes calculations of highly complex situations much simpler.
YES!
what about the Weierstrass function that isn't linear on any scale?
That is an excellent example as to why engineering uses approximations - we can closely model on a given scale any system using known functions.
I did not know about that function before though, that's super interesting!
@@woosix7735 that isn't practical so far. What is practical though is phase transition evaluation, there you cannot approximate linearly
Bravo! ! As an LA math teacher and Linear Algebra student in college, you confirmed why children need to learn Algebra-1 with the infamous Quadratic formula to understand how Linear Algebra works and is necessary to understand A.I. Please do more Linear Algebra videos for high school and college students and other interested lay people. Many Thanks.
Adequate density of new information, and sublime narrative. Also, on point visuals
This is exactly what i needed. Subscribed
the quality on this editing is top notch, congratulations!!!
This is a world class video. Thanks for posting this and keep it up!
you've GOT to post more, this stuff is amazing, im still in high school but learning about so-called 'mature' processes which become completely revolutionised really inspires me, thanks for this :)
As hobbyist mathematician, please, don’t say that f(x) is a function or worse : a linear function.
f(x) is a number in most cases you described. f on the other hand is a function and f can be linear
f(x) can be a matrix or even a function (that is what we call in computer programming higher order function) but I don’t think that was the intended message
As a published computer scientist, your videos are awesome. Appreciate the honesty that you caveat details on topics you're not 100% sure on
Getting the experts to approve is the standard I aim for, so it means a lot to hear this from you - thank you!
Lovely type, great clarity .
I think you made the best numerical linear algebra in the world, we really need more content like this. Keep up the good work.
this channel is GOLD, please keep it up we love you
Masterful explaination, going through the math and providing high-level abstractions of concepts. Really helps seeing how someone could invent a major discovery.thanks
As a grad student in theoretical machine learning, I have to say i'm blown away by the quality of your content, please keep videos like these coming !
Oh my god, this forms a small part of my PhD thesis where I've been trying to understand LAPACK's advantage/disadvantage when it comes to inverting matrices. Having this video really helps me put things into contex! Thank you very much for making this!
Great video! One thing: “processor registers” not “registries”
I know.. lol damn it
lol, I caught that same thing.
Great and clear video!
Makes me wanna study more numerical LA...combined with probability theory
because it shows how likely inefficient many algorithms use currently are, and that randomized algorithms are usually insanely much faster, while being approximately correct.
So those randomized algorithms basically can be used anywhere when we don't need to be 100% sure about the result (which is basically always, because our mathematical models are only approximations of what's going on in the world and thus are inaccurate anyways and as you mentioned, if data is used, it's noisy).
Even just the history section of this video is *incredibly* valuable, IMHO. Thank you so much!
Outstanding content, instant sub. Keep up the good work!
linearity @ 4:43 is diffirent linearity. linear functions in the sense of linear algebra must always pass through (0,0)
I thought so too, the 2D line shown on the right is an affine function, not a linear function in the rigorous sense.
Yep, otherwise the linearity of addition and multiplication which he just skipped over wouldn't apply and thus wouldn't be linear functions, or rather the correct term is linear map/transformation. Example: F(x,y,z) = (2x+y, 3y, z+5), (0,0,0) = F(0,0,0) is incorrect because F(0,0,0) = (0,0,5). The intent is to preserve the linearity of these operations so they can be applied similarly. If I want 2+2 or 2*2 I can't have 5
Incredible video with very good animations and script. Thank you !
Amazing video!
Being a comp sci undergrad, i felt like this vid was exceptionally explained. Really gives me interest in diving deeper in the topic. Thanks!
Excellent video! This topic is not easy for the layperson (admittedly, the layperson that likes Linear Algebra), but it was clearly and very well structured.
The math presentation and explanation alone was worth a sub, let alone the interesting topic.
Wow, so much research went into this! It makes me even more motivated to read papers and produce videos 😀
Awesome video
This is a really well made video, nice!
Excellent video, really well paced.
Great video, very useful and very well presented. Thank you.
Loving it loving it loving it!! Amazing video, amazing topic 👏
Amazing video with great presentation. Thank you
No better way to start the day than with an MI upload 🥳
Thank you, love hearing that!
This is a really good video 💯
thanks a ton! this was eye-opening 😊
Amazing video. Had me hooked from start to finish. You gained a new subscriber
Great video ! I had a compressive sensing class this semester, it sure is a very interesting and promissing topic of reasearch !
But I'm not sure that video games would benefit a lot from it ? If I understood correctly, the gains are mostly at high dimension, while video games linear algebra is basically only 3D, do you have exemples ? Thanks again !
Thank you! My take is that that’s only in a certain representation. E.g. when a dimension refers to a specific pixel, the dimensions are quite high.
I've been through some basic linear algebra courses, but really the covariance problem struck me as one obviousness to a statician. A statician would never go and sample everybody, they would first determine how accurate they needed to be in their certainty, and then go about sampling exactly the number of people that satisfies that equation. I actually had to do this in my job! I can totally see how this will be a great tool used with data prediction and maybe hardware accelerators to make MASSIVE gains. We are in for a huge wild ride! Thanks for the video!
you are very talented. I like your videos a lot. Keep up the hard work man!
Reminds me of what my high school maths teacher said about being able to assess product quality on a production line with high accuracy by only sampling a few percent of the product items.
Great video brother! 😍
Thank you MLST! You're among a rare bunch providing non-hyped or otherwise crazy takes on AI/ML, so it means a lot coming from you.
Fascinating. Thanks very much for filling us then on this.
why did i not found your channel before ! some channel steal my view time, but yours get me 10 years younger discovering a new domain :) i feel i m going to buy some books and papers again ! thank you!
It is decades since I delved into this stuff. You have excited me to crawl out from under the rock and read the papers.
Whenever randomness is involved you got me wanting to use Analogue processors for fast and low-power processing
I love how you explain things with no assumptions, but also don’t assume we know nothing. You let us walk in the field without getting lost in the weeds🤙
Very nice video and it's indeed a very interesting promising direction for many applications where it doesn't matter if it's not exact as long as the answer is correct to an acceptable error margin, I especially like the start with UE5 because games and especially graphics has been one area where using randomness and shortcuts to get "close enough fast enough" has always been a priority. It'd be absolutely amazing to have a RandNLA library with basically a "Speed Accuracy" slider.
I'm rooting for it. It may be awhile but considering the gains, I suspect it must arrive eventually.
I don’t know how long it took for you to create this video with fancy slides and examples, but everything is so well explained that I wish I had you as my teacher
The trick of multiplying by random S in argmin (SAx-Sb)^2 reminds me of the similar trick in the Freivalds' algorithm: instead of verifying matrix multiplication A*B==C we check A*B*x==C*x for a random vector x.
Random projections FTW???
Sounds like it!
"And if you aren't, you're probably doing something wrong." So very very true. Don't roll your own NLA code. You won't get it right and it certainly won't be faster. The corollary is "If you're inverting a matrix, you're probably doing something wrong." But that's a different problem I have to solve with newbies.
Just found this channel, great work
The first program I fed a computer was one I wrote in FORTRAN IV. It almost exhausted the memory capacity of the IBM machine, which was about 30 KBytes for the user (it used memory overloads, which we'd call banked memory today, in order to not exceed the available memory for programs).
Some small correction:
At 4:50, assuming the plotted values follow y=f(x), f is actually not linear, since in the graph we see that f(0)/=0.
At 8:22, you incorrectly refer to the computer's registers as "registries", but more importantly, data access speed depends much more on cache size than register size, as the latter can generally only hold 1-4 values (32-bit float in 128-bit register), which, while allowing the use of SIMD, is very restrictive in its use. A computer's cache is some intermediate between CPU and disk, which, if used efficiently, can indeed greatly reduce runtime.
Very interesting content! I did find that the video felt longer than expected. I was intrigued by the thumbnail and the promise of at least 10x speed improvement. However, it took quite a while to get to the papers and even longer to get to the explanation. The history definitely deserves its own video and most chapters could be much shorter.
Let me try to phrase it for people who have no math degree education, but rather engineering level: You effectively select the best fitting equations of the linear problem which is originally highly overdefined for your x vector to sufficiently represent the complete system with a small subset of the original equations. - correct? That's not directly "inducing random noise" but rather a simplification by omission of probably irrelevant equations.
This reminds me of how we did such a scheme for a "bundle block adjustment" application: We used the drastic performance boost from simplification to do multiple simple bba within each reaction step of the system with different drastically simplified subsets from the data, to then compare the results with the expected outcome (low rest error, good alignment with the continuation of the coordinates of our x vector from the previous step), then performing a final selection based on those outcomes and then performing a final error minimizing solving with those perfectly selected equations. That gives the best from both worlds: Speed up but without sacrificing correctness.
And there is no magic at all (and no "introduced random noise"). Just a "try simple" first iteration, then based on that a selected final iteration. Basically engineering optimization based on working standard linear algebra systems.
Awesome presentation, thank you!
Nearly 7 years ago when I was still a practicing geneticist, sequenced DNA would usually only be a few nucleotides long, maybe 50, and it would have to get mapped to a genome with billions of possible locations to test. The fastest algorithms ended up being used in the most published papers, so competition was pretty fierce to be the fastest.
The gold standard was a deterministic program called BWA/Bowtie, but just before I left the field a new breed of non-deterministic aligners with mapping times orders of magnitude faster were developed, and it really split opinions. Different deterministic programs would give different results (i.e. they had noise/error too, even if they're consistent about it), so in many ways who cared if a program gave different results every time you ran it, particularly if you only intend to run it once...
But there were other problems. You couldn't create definitive analyses anymore, you couldn't retrace someone else's steps, you couldn't rely on checksums, total nightmare.
The "hidden structures" aspect of the paper was interesting, the structures are in the data, and how the algorithm interacts with the data, which as the programmer you don't have access to by definition - but you also kinda know all you need to know about it too. It feels very similar to making a good meme.
As always great (very educative) content. I very much appreciate all the work you put into those videos!
it's really mind-blowing how random numbers can achieve something such fast
What a terrific video and channel. Great work! Subbed.
Worth pointing out that there is a modern sparse linear algebra package called GraphBLAS, that can be used not just for graphs (which generalize to sparse matrices) but also to any sparse matrix multiplication operation.
I understood this. Thank you, great education!
That's a win!!
Does it mean to random sample rows from the tall matrix, with low least square errors as loss indicator (Monte Carlo method?), then to work on later stages with the newly constructed "short matrix" - such as full rank square matrix with dimension of the original columns?
I see what you're going for, and that's in the style of some of the approaches taken when the field was younger. 'row-sampling' or 'column-sampling'. The problem is, the relevant information isn't uniformly distributed (a row of all zeros isn't the same as a row with wildly different numbers). So you have to mix the information from rows or columns together, and that's what is essentially done with the matrix multiplication SA.
@@Mutual_Information Agreed. Distribution shift is the bad guy behind. But uniform sampling is the best choice as you will never know the real distribution.
Nice video! Nice channel! The complicated part isn't multiplying ... it's inverting!
Hi DJ!
I love improvements in algorithmic efficiency.
Phenomenal! But I have one correction for (25:33): Full rank isn't restricted to square [invertible] matrices, it just means rank = min(m,n) rather than rank = k < min(m,n).
Whoa - very cool stuff !!
An excellent presentation.
Steve Brunton mentioned! 🎉 His channel is awesome
Do you know LightOn's OPU (Optical Processing Unit)? It can do one simple thing, multiplying with a random matrix, but it can do it lightning fast (cause it uses light). It seems like ideal hardware for this.