Is the Future of Linear Algebra.. Random?

แชร์
ฝัง
  • เผยแพร่เมื่อ 11 พ.ค. 2024
  • The machine learning consultancy: truetheta.io
    Want to work together? See here: truetheta.io/about/#want-to-w...
    "Randomization is arguably the most exciting and innovative idea to have hit linear algebra in a long time." - First line of the Blendenpik paper, H. Avron et al.
    Follow up post: truetheta.io/concepts/linear-...
    SOCIAL MEDIA
    LinkedIn : / dj-rich-90b91753
    Twitter : / duanejrich
    Github: github.com/Duane321
    SUPPORT
    / mutualinformation
    SOURCES
    Source [1] is the paper that caused me to create this video. [3], [7] and [8] provided a broad and technical view of randomization as a strategy for NLA. [9] and [12] informed me about the history of NLA. [2], [4], [5], [6], [10], [11], [13] and [14] provide concrete algorithms demonstrating the utility of randomization.
    [1] Murray et al. Randomized Numerical Linear Algebra. arXiv:2302.11474v2 2023
    [2] Melnichenko et al. CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT). arXiv:2311.08316v1 2023
    [3] P. Drineas and M. Mahoney. RandNLA: Randomized Numerical Linear Algebra. Communications of the ACM. 2016
    [4] N. Halko, P. Martinsson, and J. Tropp. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. arXiv:0909.4061v2 2010
    [5] Tropp et al. Fixed Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data. NeurIPS Proceedings. 2017
    [6] X. Meng, M. Saunders, and M. Mahoney. LSRN: A Parallel Iterative Solver for Strongly Over- Or Underdetermined Systems. SIAM 2014
    [7] D. Woodruff. Sketching as a Tool for Numerical Linear Algebra. IBM Research Almaden. 2015
    [8] M. Mahoney. Randomized Algorithms for Matrices and Data. arXiv:1104.5557v3. 2011
    [9] G. Golub and H van der Vorst. Eigenvalue Computation in the 20th Century. Journal of Computational and Applied Mathematics. 2000
    [10] J. Duersch and M. Gu. Randomized QR with Column Pivoting. arXiv:1509.06820v2 2017
    [11] Erichson et al. Randomized Matrix Decompositions Using R. Journal of Statistical Software. 2019
    [12] J. Gentle et al. Software for Numerical Linear Algebra. Springer. 2017
    [13] H. Avron, P. Maymounkov, and S. Toledo. Blendenpik: Supercharging LAPACK's Least-Squares Solver. Siam. 2010
    [14] M. Mahoney and P. Drineas. CUR Matrix Decompositions for Improved Data Analysis. Proceedings of the National Academy of Sciences. 2009
    TIMESTAMPS
    0:00 Significance of Numerical Linear Algebra (NLA)
    1:35 The Paper
    2:20 What is Linear Algebra?
    5:57 What is Numerical Linear Algebra?
    8:53 Some History
    12:22 A Quick Tour of the Current Software Landscape
    13:42 NLA Efficiency
    16:06 Rand NLA's Efficiency
    18:38 What is NLA doing (generally)?
    20:11 Rand NLA Performance
    26:24 What is NLA doing (a little less generally)?
    31:30 A New Software Pillar
    32:43 Why is Rand NLA Exceptional?
    34:01 Follow Up Post and Thank You's

ความคิดเห็น • 376

  • @charilaosmylonas5046
    @charilaosmylonas5046 หลายเดือนก่อน +252

    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! :)

    • @howuhh8960
      @howuhh8960 หลายเดือนก่อน +8

      it didn't because all efficient variations have significantly worse performance on retrieval tasks (associative recall for example), as all recent papers demonstrated

    • @Arithryka
      @Arithryka 28 วันที่ผ่านมา

      The Quadratic Memory Cost of Self-Attention in Transformers is my new band name

  • @BJ52091
    @BJ52091 หลายเดือนก่อน +438

    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!

    • @Mutual_Information
      @Mutual_Information  หลายเดือนก่อน +35

      Great to have you here!

    • @purungo
      @purungo หลายเดือนก่อน +39

      So you're saying there's a 1 chance in roughly 10^16300 that you're giving him 3 thumbs up...

    • @frankjohnson123
      @frankjohnson123 29 วันที่ผ่านมา +6

      My brother in Christ, use a discrete probability distribution.

    • @nile6076
      @nile6076 29 วันที่ผ่านมา +11

      Only if you assume a normal distribution! ​@@purungo

    • @sylv256
      @sylv256 28 วันที่ผ่านมา +2

      Is this just one big late april fool's? What the hell

  • @octavianova1300
    @octavianova1300 หลายเดือนก่อน +738

    reminds me of that episode of veggie tales when larry was like "in the future, linear algebra will be randomly generated!"

    • @NoNameAtAll2
      @NoNameAtAll2 หลายเดือนก่อน +49

      W E E D E A T E R

    • @rileymurray7437
      @rileymurray7437 หลายเดือนก่อน +13

      Reminds you of what???

    • @jedediahjehoshaphat
      @jedediahjehoshaphat หลายเดือนก่อน +7

      xD

    • @Godfather-qr6ej
      @Godfather-qr6ej หลายเดือนก่อน +3

      I thought it would be some nice science show, but it turns out to be some kids show : (

    • @notsojharedtroll23
      @notsojharedtroll23 หลายเดือนก่อน

      ​@@rileymurray7437 he means this video: th-cam.com/video/j4Ph02gzqmY/w-d-xo.htmlsi=wb2atwfoSQaefrjL

  • @laurenwrubleski7204
    @laurenwrubleski7204 หลายเดือนก่อน +252

    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.

    • @sucim
      @sucim 29 วันที่ผ่านมา +15

      but can your cards train imagenet without crashing?

    • @389martijn
      @389martijn 29 วันที่ผ่านมา +11

      ​@@sucimsheeeeeeeeesh

    • @johnothwolo
      @johnothwolo 28 วันที่ผ่านมา

      Are you guys hiring?

    • @Zoragna
      @Zoragna 28 วันที่ผ่านมา

      OP forgot about BLAS being a standard so most implementations have been forgotten, it's weird to point at Nvidia

    • @cannaroe1213
      @cannaroe1213 28 วันที่ผ่านมา +9

      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.

  • @TimL_
    @TimL_ หลายเดือนก่อน +113

    The part about matrix multiplication reminded me of studying cache hit and miss patterns in university. Interesting video.

  • @charlesloeffler333
    @charlesloeffler333 หลายเดือนก่อน +56

    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

  • @scottmiller2591
    @scottmiller2591 หลายเดือนก่อน +80

    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.

    • @Mutual_Information
      @Mutual_Information  หลายเดือนก่อน +16

      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.

    • @ajarivas72
      @ajarivas72 20 วันที่ผ่านมา

      @@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.

    • @skn123
      @skn123 วันที่ผ่านมา +1

      Halko's algorithm helped me start my understanding of Laplacian eigenmaps and other dimensionality reduction methods.

  • @danielsantiagoaguilatorres9973
    @danielsantiagoaguilatorres9973 หลายเดือนก่อน +36

    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

  • @pietheijn-vo1gt
    @pietheijn-vo1gt หลายเดือนก่อน +38

    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

    • @tamineabderrahmane248
      @tamineabderrahmane248 หลายเดือนก่อน

      random sampling to reconstruct the signal

    • @pietheijn-vo1gt
      @pietheijn-vo1gt หลายเดือนก่อน

      @@tamineabderrahmane248... what?

    • @MrLonelyrager
      @MrLonelyrager 29 วันที่ผ่านมา +2

      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.

    • @pietheijn-vo1gt
      @pietheijn-vo1gt 28 วันที่ผ่านมา

      @@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

  • @richardyim8914
    @richardyim8914 หลายเดือนก่อน +22

    Golub and Van Loan’s textbook is goated. I loved studying and learning numerical linear algebra for the first time in undergrad.

  • @zyansheep
    @zyansheep หลายเดือนก่อน +15

    Dang, I absolutely love videos and articles that summarize the latest in a field of research and explain the concepts well!

  • @makapaka8247
    @makapaka8247 หลายเดือนก่อน +56

    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!

  • @charlesity
    @charlesity 27 วันที่ผ่านมา +7

    As always this is BRILLIANT. I started following your videos since I saw the GP regression video. Great content! Thank you very much.

  • @noahgsolomon
    @noahgsolomon หลายเดือนก่อน +5

    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

  • @KipIngram
    @KipIngram หลายเดือนก่อน +6

    Fascinating. Thanks very much for filling us then on this.

  • @marcegger7411
    @marcegger7411 29 วันที่ผ่านมา +5

    Damn... your videos are getting beyond excellent!

  • @bluearctik3980
    @bluearctik3980 28 วันที่ผ่านมา +4

    My first thought was "this is like journal club with DJ"! Great stuff - well researched and crisply delivered. More of this, if you please.

  • @aleksszukovskis2074
    @aleksszukovskis2074 หลายเดือนก่อน +5

    its always a pleasure to watch this channel

  • @deltaranged
    @deltaranged หลายเดือนก่อน +22

    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!

    • @Rockyzach88
      @Rockyzach88 หลายเดือนก่อน +1

      TH-cam has you in its palms. _laughs maniacally_

    • @Sino12
      @Sino12 หลายเดือนก่อน

      where do you study?

  • @mgostIH
    @mgostIH หลายเดือนก่อน +6

    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!

  • @bn8ws
    @bn8ws 23 วันที่ผ่านมา +1

    Outstanding content, instant sub. Keep up the good work!

  • @AjaniTea
    @AjaniTea 13 วันที่ผ่านมา +1

    This is a world class video. Thanks for posting this and keep it up!

  • @JoeBurnett
    @JoeBurnett 29 วันที่ผ่านมา +2

    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!

  • @wiktorzdrojewski890
    @wiktorzdrojewski890 หลายเดือนก่อน +2

    this feels like a good presentation topic for numerical methods seminar

  • @gaussology
    @gaussology 25 วันที่ผ่านมา

    Wow, so much research went into this! It makes me even more motivated to read papers and produce videos 😀

  • @piyushkumbhare5969
    @piyushkumbhare5969 หลายเดือนก่อน +1

    This is a really well made video, nice!

  • @jondor654
    @jondor654 29 วันที่ผ่านมา +2

    Lovely type, great clarity .

  • @from_my_desk
    @from_my_desk หลายเดือนก่อน +1

    thanks a ton! this was eye-opening 😊

  • @AlexGarel-xr9ri
    @AlexGarel-xr9ri 26 วันที่ผ่านมา

    Incredible video with very good animations and script. Thank you !

  • @EkShunya
    @EkShunya หลายเดือนก่อน

    Been a while since ur last post
    thanks
    Please make more often
    I like what u make

  • @braineaterzombie3981
    @braineaterzombie3981 28 วันที่ผ่านมา +1

    This is exactly what i needed. Subscribed

  • @ernestoherreralegorreta137
    @ernestoherreralegorreta137 28 วันที่ผ่านมา +3

    Amazing explanation of a complex topic! You've got yourself a new subscriber.

  • @Stephen_Kelley
    @Stephen_Kelley 22 วันที่ผ่านมา +1

    Excellent video, really well paced.

  • @lbgstzockt8493
    @lbgstzockt8493 หลายเดือนก่อน +5

    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.

  • @moisesbessalle
    @moisesbessalle หลายเดือนก่อน +6

    Amazing video!

  • @JonathanPlasse
    @JonathanPlasse 21 วันที่ผ่านมา +1

    Awesome presentation, thank you!

  • @Otakutaru
    @Otakutaru 19 วันที่ผ่านมา +1

    Adequate density of new information, and sublime narrative. Also, on point visuals

  • @tiwiatg2186
    @tiwiatg2186 13 วันที่ผ่านมา +1

    Loving it loving it loving it!! Amazing video, amazing topic 👏

  • @MachineLearningStreetTalk
    @MachineLearningStreetTalk หลายเดือนก่อน +5

    Great video brother! 😍

    • @Mutual_Information
      @Mutual_Information  หลายเดือนก่อน

      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.

  • @oceannuclear
    @oceannuclear 25 วันที่ผ่านมา

    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!

  • @tantzer6113
    @tantzer6113 หลายเดือนก่อน +1

    I enjoyed this video. Thank you.

  • @billbez7465
    @billbez7465 13 วันที่ผ่านมา +1

    Amazing video with great presentation. Thank you

  • @iamr0b0tx
    @iamr0b0tx หลายเดือนก่อน +4

    This is a really good video 💯

  • @hozaifas4811
    @hozaifas4811 หลายเดือนก่อน +23

    We need more content creators like you ❤

    • @Mutual_Information
      @Mutual_Information  หลายเดือนก่อน +4

      Thank you. These videos take awhile, so I wish I could upload more. But I'm confident I'll be doing TH-cam for a long time.

    • @hozaifas4811
      @hozaifas4811 หลายเดือนก่อน +2

      @@Mutual_Information Well ,This news made my day !

  • @CyberBlaster-fu2dz
    @CyberBlaster-fu2dz หลายเดือนก่อน +1

    Great video, thank you!

  • @Pedritox0953
    @Pedritox0953 หลายเดือนก่อน +2

    Great video!

  • @pygmalionsrobot1896
    @pygmalionsrobot1896 หลายเดือนก่อน +2

    Whoa - very cool stuff !!

  • @scottmiller2591
    @scottmiller2591 หลายเดือนก่อน +7

    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.

    • @Mutual_Information
      @Mutual_Information  หลายเดือนก่อน +4

      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!

    • @scottmiller2591
      @scottmiller2591 หลายเดือนก่อน

      @@Mutual_Information Agree absolutely!

    • @rileyjohnmurray7568
      @rileyjohnmurray7568 หลายเดือนก่อน +3

      Jim Demmel and Jack Dongarra pronounced it "blahs" the last time I spoke with each of them. (~This morning and one month ago, respectively.) 😉

    • @Mutual_Information
      @Mutual_Information  หลายเดือนก่อน +1

      @@rileyjohnmurray7568 lol

    • @scottmiller2591
      @scottmiller2591 หลายเดือนก่อน +1

      @@rileyjohnmurray7568 I hope they perk up ☺

  • @broccoli322
    @broccoli322 หลายเดือนก่อน +4

    Great stuff

  • @the_master_of_cramp
    @the_master_of_cramp หลายเดือนก่อน +2

    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).

  • @EE-wo5ty
    @EE-wo5ty หลายเดือนก่อน +5

    the quality on this editing is top notch, congratulations!!!

  • @vNCAwizard
    @vNCAwizard 23 วันที่ผ่านมา +1

    An excellent presentation.

  • @nikita_x44
    @nikita_x44 หลายเดือนก่อน +4

    linearity @ 4:43 is diffirent linearity. linear functions in the sense of linear algebra must always pass through (0,0)

    • @sufyanali3992
      @sufyanali3992 26 วันที่ผ่านมา

      I thought so too, the 2D line shown on the right is an affine function, not a linear function in the rigorous sense.

    • @KepleroGT
      @KepleroGT 16 วันที่ผ่านมา

      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

  • @antiguarocks
    @antiguarocks 11 วันที่ผ่านมา +1

    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.

  • @Geenimetsuri
    @Geenimetsuri 3 วันที่ผ่านมา +1

    I understood this. Thank you, great education!

  • @DawnOfTheComputer
    @DawnOfTheComputer 18 วันที่ผ่านมา +1

    The math presentation and explanation alone was worth a sub, let alone the interesting topic.

  • @Ohmriginal722
    @Ohmriginal722 หลายเดือนก่อน +1

    Whenever randomness is involved you got me wanting to use Analogue processors for fast and low-power processing

  • @ShivaTD420
    @ShivaTD420 21 วันที่ผ่านมา +2

    If you take white noise. And put a filter on it. You can produce every note, because every tone and semi tone is in the noise.

  • @damondanieli
    @damondanieli หลายเดือนก่อน +6

    Great video! One thing: “processor registers” not “registries”

  • @TrungHieuTu
    @TrungHieuTu หลายเดือนก่อน +1

    Very useful, thanks

  • @wafikiri_
    @wafikiri_ 17 วันที่ผ่านมา

    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).

  • @michaeln.8185
    @michaeln.8185 หลายเดือนก่อน +2

    Great video! Thank you for producing this!

  • @user-le1ho7sl7h
    @user-le1ho7sl7h 6 วันที่ผ่านมา

    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.

  • @pr0crastinatr
    @pr0crastinatr หลายเดือนก่อน +1

    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.

  • @General12th
    @General12th หลายเดือนก่อน +3

    Hi DJ!
    I love improvements in algorithmic efficiency.

  • @johannguentherprzewalski
    @johannguentherprzewalski 26 วันที่ผ่านมา

    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.

  • @h.b.1285
    @h.b.1285 หลายเดือนก่อน +1

    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.

  • @metromap9618
    @metromap9618 หลายเดือนก่อน

    great video!

  • @chakrasamik
    @chakrasamik หลายเดือนก่อน +1

    Excellent ❤

  • @Dagobah359
    @Dagobah359 25 วันที่ผ่านมา +5

    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.

  • @ihatephysixs
    @ihatephysixs 25 วันที่ผ่านมา +2

    Awesome video

  • @DavidS-ji6qv
    @DavidS-ji6qv 26 วันที่ผ่านมา

    Phenomenal video

  • @RepChris
    @RepChris 4 วันที่ผ่านมา +1

    Of course i get this in my recommended a few days after my first numerical analysis lecture

    • @RepChris
      @RepChris 4 วันที่ผ่านมา +1

      Which is a course i picked up (its semi-required) since it seems like a very useful thing to understand properly, even though i am not the best at advanced linear algebra and have PTSD from a previous professor and get a visceral reaction every time i see an epsilon, both of which are integral to most of the course

    • @Mutual_Information
      @Mutual_Information  วันที่ผ่านมา

      Well I hope math TH-cam serves as a bit of PTSD therapy. I hope a shit professor doesn't get the way of you enjoying a good thing.

  • @0x4849
    @0x4849 วันที่ผ่านมา

    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.

  • @StratosFair
    @StratosFair 26 วันที่ผ่านมา

    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 !

  • @ryanjkim
    @ryanjkim 4 วันที่ผ่านมา +1

    Really great thank you.

  • @MariusKavaliauskas
    @MariusKavaliauskas หลายเดือนก่อน

    Very informative video and I will be waiting for more. I am hooked on randomized linear algebra since Ewin Tang "dequantization" papers. I wonder if randomized algos will have huge impact on ML training performance (not just inference). I also wonder how will it compare in performance and accuracy: low-rank approximations of ML models vs randomized inference on full models.

  • @nonamehere9658
    @nonamehere9658 หลายเดือนก่อน +3

    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???

  • @psl_schaefer
    @psl_schaefer หลายเดือนก่อน +1

    As always great (very educative) content. I very much appreciate all the work you put into those videos!

  • @robmorgan1214
    @robmorgan1214 หลายเดือนก่อน +3

    Of course. This isn't a surprise. I've been using these techniques for optimization for a long time. Simulated annealing was proven (decades ago) to scale better than many optimization algorithms. If your big O is bigger than Sim annealing, use sim annealing! Always calculate your big O and THEN measure your implementation to make sure you hit it. Same thing goes for your error... and controlling that can blow out your big O and that's data not algorithm dependent! ALWAYS MEASURE! If you have to pre sort before accumulating to minimize error you are not going to hit your scaling numbers and you're going to murder your cache and memory pipelining. The key with that 1/e term is to recall that floating point math is going to accumulate rounding errors at a precision of about 0.1-1.0 in 1M. This sets your floor and the sensitivity of your eigenvalues ( if they vary by more than about one part in 1M, your answers will be dominated by errors, so you take the hit and use doubles). This kind of stuff used to be explicitly covered in scientific computing classes when resources were limited and the hardware was MUCH less complex. It's interesting that this complexity has managed to hide potential optimizations of order 20-1000 x. But it makes sense, in order to use the HW efficiently you need to be an expert in so many things that the problems you're actually trying to solve becomes something of an afterthought and resources allocation in universities and other organizations focused on numerical methods face the pressures of silos and hyperspecialization. Conaway's law strikes again, as our software matches the organizational structures that create it.

    • @modernsolutions6631
      @modernsolutions6631 3 วันที่ผ่านมา

      simulated annealing is about something else entirely as it's a black box optimisation problem. You sound a bit unhinged. 😢

    • @robmorgan1214
      @robmorgan1214 3 วันที่ผ่านมา

      @@modernsolutions6631 I've got a PhD and have been using this technique to solve or accelerate various problems like this since I was a student. The ORIGIN of simulated annealing is metropolis hastings, where you try accelerating the integration of a stiff differential equation by adjusting the range of the rejection interval in a rapidly changing zone of the equation. If you adjust this on the fly algorithmically and familiarize yourself with the mathematical properties of the logistic distribution you got simulated annealing. This is a similar process to how they approach solving many problems in courses on convex optimization by reframing the form of the problem. This is a useful but unnecessary step. In this case they are exploiting their ability to do a "fast" step along with NlogN scaling instead of doing N^3 calculations where the mismatch in the scale of variou eigenvalues can lead to error accumulation. In the guess and check approach you don't accumulate error at the same rate so it can lead to faster solutions at higher precision with less polishing. Long story short its the same stuff as sim annealing... just seen from a different vantage, like solvig a problem using duality.

  • @mohammedbelgoumri
    @mohammedbelgoumri หลายเดือนก่อน +4

    No better way to start the day than with an MI upload 🥳

  • @nandanshettigar7261
    @nandanshettigar7261 22 วันที่ผ่านมา +1

    Another beautiful global optima of priceless information to pull me out of my local tunnels :) Thank you as always

  • @catcoder12
    @catcoder12 หลายเดือนก่อน +1

    anotha banger by DJ

  • @janni7439
    @janni7439 20 วันที่ผ่านมา

    There are also other approaches where you choose for an epsilon and reduce complexity of the problem, like in hierarchical matrices

  • @baptiste-genest
    @baptiste-genest หลายเดือนก่อน +4

    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 !

    • @Mutual_Information
      @Mutual_Information  หลายเดือนก่อน +3

      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.

  • @maxheadrom3088
    @maxheadrom3088 10 วันที่ผ่านมา

    Nice video! Nice channel! The complicated part isn't multiplying ... it's inverting!

  • @pythonguytube
    @pythonguytube 25 วันที่ผ่านมา

    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.

  • @HelloWorlds__JTS
    @HelloWorlds__JTS 15 วันที่ผ่านมา

    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).

  • @jeffreychandler8418
    @jeffreychandler8418 หลายเดือนก่อน

    This is something that I've really been wondering about at a general level. How to add pinches of randomness to improve inference, simulations, etc. I personally wonder how we could use it to improve model accuracy by specifically predicting error then building in a stochastic prediction, Might be a big change in ML and neural nets

  • @Patashu
    @Patashu หลายเดือนก่อน

    This has been my thought about deep learning for a while now - we build computers to be deterministic, but deep learning would run best on a different kind of computer that is lossy but as a tradeoff much more energy inefficient. This is a different take though (keep determinism, but instead deliberately code faster but lossy algorithms) that could also do the job,

  • @u2b83
    @u2b83 26 วันที่ผ่านมา

    I tripped across the Integer relation algorithm at 15, when I wrote a calculator program to calculate how much change you put on the scale just based on the total weight. Thanks to this video (top 10 problems list), I finally know what that's called. Until now I called this the "primeness of unique coin weights" lol

  • @minsookim-ql1he
    @minsookim-ql1he 22 วันที่ผ่านมา +1

    This is very interesting

  • @tanithrosenbaum
    @tanithrosenbaum 28 วันที่ผ่านมา +1

    "They're quite good" - Understatement of the decade 😄

  • @cannaroe1213
    @cannaroe1213 28 วันที่ผ่านมา +1

    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.

  • @HyperDevv
    @HyperDevv หลายเดือนก่อน +3

    NEW MATH UPDATE JUST DROPPED

  • @rr00676
    @rr00676 25 วันที่ผ่านมา +1

    I've been hoping some advances in probabilistic numerics and random matrix theory bring PGM's some love. Computing matmuls/inverses every iteration of MCMC makes me sad :(. As expected, great video!

  • @user-gv6fn6yt2u
    @user-gv6fn6yt2u 25 วันที่ผ่านมา +1

    it's really mind-blowing how random numbers can achieve something such fast

  • @williamchen6099
    @williamchen6099 หลายเดือนก่อน +1

    wow this is an amazingly well produced and scripted video and delivered perfectly, how long did it take you to plan and execute it?

    • @Mutual_Information
      @Mutual_Information  29 วันที่ผ่านมา

      I was working on it since November, mostly on the weekends and sometimes in the evenings. I'd guess it took me over 150 hours. The stages are reading research, script writing, creating the on screen animations, re-writing the script with feedback (e.g. from Riley here), shooting the video, editing it, adding music, cleaning it up, sharing the video for feedback. It takes a lot longer than I like to admit.

  • @midou6104
    @midou6104 20 วันที่ผ่านมา +1

    Okay, objectively, that's the hardest thing in linear algebra I've ever seen.

  • @greensock4089
    @greensock4089 หลายเดือนก่อน +32

    Plz don't put stuff we're supposed to read at the bottom of the screen, the subtitles cover them up and it's super annoying

    • @filipo4114
      @filipo4114 หลายเดือนก่อน +8

      You can drag the subtitles to the top of screen

    • @JasminUwU
      @JasminUwU หลายเดือนก่อน +9

      ​@@filipo4114 The comment still gives good advice for making accessible videos

    • @nUrnxvmhTEuU
      @nUrnxvmhTEuU 29 วันที่ผ่านมา +7

      @filipo Definitely not on the mobile web.

    • @Mutual_Information
      @Mutual_Information  27 วันที่ผ่านมา +7

      Good to know. I’ll keep it in mind next time. Thanks