[HN Gopher] Interactive Linear Algebra (2019)
___________________________________________________________________
Interactive Linear Algebra (2019)
Author : natemcintosh
Score : 254 points
Date : 2021-08-13 13:03 UTC (9 hours ago)
(HTM) web link (textbooks.math.gatech.edu)
(TXT) w3m dump (textbooks.math.gatech.edu)
| sonograph wrote:
| I hope that GATech one day offers an affordable online math MSc
| program, like their CS program
| ogogmad wrote:
| I wrote an entry on Wikipedia on visualizing the QR algorithm:
| https://en.wikipedia.org/wiki/QR_algorithm
|
| The visualization helped me spot an unstable fixed point and
| understand the behaviour of the algorithm near eigenvalue
| clashes. The behaviour's quite sophisticated.
|
| I think I wrote this there, but here goes again. The idea is that
| a positive-definite symmetric matrix can be visualized as an
| ellipse. This follows from the spectral theorem. Each iteration
| of the QR algorithm causes the ellipse to fall towards the
| x-axis, as if under the influence of gravity. The unstable fixed
| point corresponds to when the ellipse is standing up
| precariously, unable to fall in either direction. If you tilt it
| by just a bit, it will fall over (so the fixed point is
| unstable).
|
| The case when the ellipse is nearly circular (corresponding to
| near eigenvalue clashes) causes the ellipse to fall over slowly.
| I think this also makes physical sense, if you think of it being
| under the influence of gravity. If you think of this near-circle
| as being a matrix, then this matrix is nearly equal to a scalar
| multiple of the identity matrix, so its eigenvalues are
| essentially known. The fact that the ellipse falls very slowly
| implies that the eigenvectors are unstable near eigenvalue
| clashes, but the eigenvalues are easy to find.
|
| Note: The issues surrounding the unstable fixed point can be
| fixed using Wilkinson shifts. This makes each iteration into a
| discontinuous function, allowing all the fixed points to be
| stable. The issue surrounding instability of the eigenvectors
| near eigenvalue clashes cannot be fixed, as it's intrinsic to
| eigendecomposition (even of symmetric matrices). The latter
| difficulties can be dodged by slightly perturbing the matrix, but
| the resulting eigenvectors can be very different from the
| eigenvectors of the unperturbed matrix.
| gugagore wrote:
| > a positive-definite symmetric matrix can be visualized as an
| ellipse.
|
| It is clear that you mean the ellipsoid as a set of points {x |
| x^T * A * x = 1} (or some other constant). There is another way
| in which all square matrices define an ellipsoid based on how
| the matrix transforms a unit sphere: {A*x | x^T * x = 1}
| (different matrices can map to the same ellipse here, however).
|
| I always like to clarify which one.
|
| (I unfortunately do not have intuition for the QR algorithm,
| but I am distracted by the description of an ellipse falling,
| as if it's rolling against the x-axis)
| ogogmad wrote:
| > It is clear that you mean the ellipsoid as a set of points
| {x | x^T * A * x = 1} (or some other constant). There is
| another way in which all square matrices define an ellipsoid
| based on how the matrix transforms a unit sphere: {A*x | x^T
| * x = 1} (different matrices can map to the same ellipse
| here, however).
|
| I actually had the latter one in mind: The one given by {A*x
| | x^T * x = 1}. I hadn't thought of your other suggestion.
|
| > (I unfortunately do not have intuition for the QR
| algorithm, but I am distracted by the description of an
| ellipse falling, as if it's rolling against the x-axis)
|
| I don't know if this helps: https://ibb.co/DRDLzgJ
|
| Each iteration causes it to rotate around the origin. The big
| semi-axis of the ellipse makes a smaller angle with the
| x-axis on each iteration. When the semi-axes are parallel to
| the coordinate axes, the matrix is diagonal.
| gugagore wrote:
| > I actually had the latter one in mind: The one given by
| {A _x | x^T_ x = 1}.
|
| I am near certain that you did not mean this.
|
| > When the semi-axes are parallel to the coordinate axes,
| the matrix is diagonal.
|
| Let D =
|
| the matrix | 2 0 | | 0 1 |
|
| And let R be any 2-by-2 rotation matrix.
|
| A = D * R would give you a locus of points (under {A _x |
| x^T_ x = 1}) that has the semi-axes parallel to the
| coordinate axes. In general, A is not diagonal.
|
| For the condition you mention (axis-aligned semi-axes of
| ellipsoid iff matrix is diagonal) is true for {x | x^T * A
| * x = 1} .
| ogogmad wrote:
| I only consider positive semi-definite symmetric
| matrices. A = D * R is almost certainly not such a
| matrix. The positive semi-definite symmetric case is the
| only one needed to compute SVDs.
|
| A proof of convergence for the algorithm is only known
| for certain families of matrices. These include the
| positive-definite symmetric matrices, all symmetric
| matrices (once suitable improvements to the algorithm are
| made), the Hermitian matrices, and perhaps some others.
| But a proof that's valid for all matrices isn't known,
| even though the algorithm (when improved using Wilkinson
| shifts) appears to converge everywhere.
| gugagore wrote:
| Ah, okay. Sure. And PSD matrix A is diagonalizeable with
| orthogonal matrices i.e. A = Q^T * D * Q
|
| The ellipsoid visualization you meant is insensitive to
| the Q term (any rotation of a sphere is the same sphere),
| but not to the Q^T term.
|
| What I am still failing to understand is this sentence
| from the article:
|
| > The basic QR algorithm can be visualized in the case
| where A is a positive-definite symmetric matrix.
|
| It sounds like you can visualize the iterates A_{k} no
| matter what. Is the problem that there isn't a fixed
| point when the ellipsoid is axis-aligned?
|
| The article has:
|
| > Under certain conditions,[4] the matrices Ak converge
| to a triangular matrix, the Schur form of A.
|
| So am I to understand that for A positive semi-definite,
| the A_{k} converges to a diagonal matrix?
| benrbray wrote:
| Since you mentioned QR, I want to link [1] to one of my
| favorite articles, which explains how to use the QR
| decomposition to sample a random orthogonal matrix uniformly at
| random. The basic idea, of course, is that if A is a random
| matrix, and we compute A = QR, then Q is a random orthogonal
| matrix. But with what distribution? Well, it turns out to be
| almost uniform (according to Haar measure), but there are some
| density issues. A simple scaling of QR decomposition resolves
| the issue.
|
| When I was a TA I loved giving this as an example to students.
| It's a great teaser for the rabbit hole that is random matrix
| theory.
|
| [1] Mezzadri 2002, "How to Generate Random Matrices from the
| Classical Compact Groups"
| (http://www.ams.org/notices/200705/fea-mezzadri-web.pdf)
| criddell wrote:
| It would be nice if the items in the left column on the index
| page [1] were links to the _context_ location.
|
| [1]: http://textbooks.math.gatech.edu/ila/index-1.html
| testkitchen wrote:
| This is great! This is a nice direction to go. Also, I don't mind
| if the creators would like to charge a small fee to use the book.
| scythmic_waves wrote:
| I've only just skimmed through this. And it's a subject I already
| know so I can't tell if it's actually a good resource. However,
| my initial impression is that I love it.
|
| I think that textbooks, math textbooks in particular, are an
| example where print publishing does a disservice. (I'm counting
| PDFs here too.) By having to lay everything out in print form,
| you have to clutter up your explanations with examples and
| footnotes that take up physical room. Here, the examples are
| toggle-able. If I _want_ to explore an example, I can. But I
| don't need to. This kind of thing is especially helpful when
| reviewing content for, say, a test rather than learning it for
| the first time.
|
| Also finding things in textbooks is a real pain. It's difficult
| to index things in a helpful way, so you just have these counting
| schemes in LaTeX that increment for every definition, theorem,
| etc. I'd love to be able to tag things then search the tags.
|
| And that says nothing for when you want to explain something
| that's difficult with static images. Being able to interact with
| animations by zooming, panning, pausing, slowing down, speeding
| up, etc. is a boon. (I don't think I actually saw an example of a
| non-static image here, but I think my point still stands.)
|
| All in all, I'd love to see more interactive textbooks. We've got
| this really expressive kind of document via the web. I think we
| should be taking advantage of it more.
| chobytes wrote:
| I think I prefer physical textbooks for many reasons I wont get
| in to... but I do really like the interactive and visualization
| elements computers offer.
|
| I feel like teaching kids some amount of coding to be able to
| play with math could be very helpful.
| Jtsummers wrote:
| That's one of the intents behind Logo, see the book
| _Mindstorms_ by Papert.
|
| Programming wasn't an end unto itself, but a means of
| exploring complex topics. Notebook-style programming is a
| great modern iteration of this, especially with the ability
| to produce interesting and complex visualizations of the
| underlying data and structures.
| chobytes wrote:
| Yup, notebooks are what I had in mind. I make heavy use of
| mathematica when I want to explore a new topic.
| Koshkin wrote:
| > _an example where print publishing does a disservice_
|
| What would be an example (in the area of learning) where it
| does not? In the age of pervasive computing printed text is
| just that - a printout. A screenshot, if you will. Not
| extremely useful. Even a basic 3D model of something (like a
| car engine) that you could simply rotate and zoom is immensely
| more informative than a static picture of the same object.
|
| Text, such as a mathematical proof, too, could be made dynamic
| for the benefit of the student: you could hide or show
| references, insert notes, etc.
|
| Static/printed content is merely an artifact of the past
| technology we continue clinging to for no good reason.
|
| To say nothing about the environmental impact.
| AlotOfReading wrote:
| Professional color books (e.g. the Munsell soil books [1])
| are a good example here. Screens use different, more
| restricted color spaces and are additive rather than
| subtractive. I also have some books where the opposing page
| is used to hold the corresponding translation, so you can see
| both the original and its translation simultaneously. That
| breaks the page-at-a-time model of most document readers.
|
| [1] https://www.amazon.com/Munsell-Soil-Book-
| Color-M50215B/dp/B0...
| JadeNB wrote:
| > I think that textbooks, math textbooks in particular, are an
| example where print publishing does a disservice. (I'm counting
| PDFs here too.) By having to lay everything out in print form,
| you have to clutter up your explanations with examples and
| footnotes that take up physical room. Here, the examples are
| toggle-able. If I _want_ to explore an example, I can. But I
| don't need to. This kind of thing is especially helpful when
| reviewing content for, say, a test rather than learning it for
| the first time.
|
| This sounds so much like a meeting of Lamport's idea of how to
| structure a proof
| (https://lamport.azurewebsites.net/pubs/proof.pdf) and the
| Stacks project (https://stacks.math.columbia.edu).
| ai_ia wrote:
| > I think that textbooks, math textbooks in particular, are an
| example where print publishing does a disservice. (I'm counting
| PDFs here too.) By having to lay everything out in print form,
| you have to clutter up your explanations with examples and
| footnotes that take up physical room. .
|
| I agree with your sentiment. Although, I believe there is bit
| of problem of generalizing it to a wider field. Surely, you can
| make explorables with Linear Algebra, Trigonometry, Geometry,
| Number Theory etc, but there still exists a lot of mathematical
| fields, where such explanation using visualization is pretty
| difficult. It takes a lot of time to come up good explanations,
| while even longer for interactive explorables.
|
| > All in all, I'd love to see more interactive textbooks. We've
| got this really expressive kind of document via the web. I
| think we should be taking advantage of it more.
|
| This is something I have spent the last 4 years of my life
| building. I designed an alternative way of writing interactive
| books that takes a different approach than using just
| explorables. It's a conversational way of learning subjects
| designed for auto-didacts.
|
| You interact (converse?) with the book and learn gradually. You
| can of course embed explorables into it (which I am planning to
| for upcoming linear algebra / discrete mathematics course), but
| the general process can still be generalized to _any_ field.
| And if you are a LaTeX fan, you are in luck as all your notes
| are compiled as a Tufte-Latex Notebook. The medium is called
| Primer, homage to the diamond age.
|
| You can checkout Primer here https://primerlabs.io.
|
| A comic-based guide to understand how Primer helps you learn
| effectively: https://primerlabs.io/comics/introducing-primer-
| comics/
| dragonvspanda wrote:
| I loved the comic. Have signed up. Will be looking forward
| your future courses.
| trees101 wrote:
| Great work, thank you. Have you considered Obsidian, and
| Obsidian publish, as a medium? Take a look at Andy
| Matuschak's site as one example, there are many variants out
| there too https://notes.andymatuschak.org/About_these_notes
| master_yoda_1 wrote:
| It's confusing why ml beginners are obsessed over linear algebra.
| The subject is very hard and need only for advanced ml model. why
| not just study calculus and understand it?
| nla wrote:
| FYI, FB blocks this as "violating community standards" when you
| try to post it there.
|
| And also, it's awesome!
| ampgt wrote:
| Cool to see an article on the front page of HN from my alma mater
| :)
| whytaka wrote:
| Being aware of the broad applications for Linear Algebra in
| engineering, I'm very eager to go through some Linear Algebra
| course on my own. But my problem is that I can't just learn from
| a text, even if it's interactive. I need to apply it to
| something.
|
| What are some fun projects that uses LA for an individual? I'm
| thinking about things like generative art, if anyone knows of any
| artists that inspire them.
| ampgt wrote:
| Check out "eigenfaces." It's straight forward and works
| reasonably well. There are a lot of interesting applications of
| PCA and SVD. Signal and noise separation, machine learning, the
| list goes on.
| gugagore wrote:
| One possible perspective: thinking of images as a vector space,
| and thinking of image operations like blurring, sharpening, and
| even any spatial transformation as linear operators
| (representable as matrices).
|
| This perspective is most straightforward with a 1-dimensional
| domain, like an audio signal, or the temperature along a thin
| rod, because there's a clear way to organize all the values in
| a vector, e.g. all the audio samples are just in sequence. So
| if that's appealing to you at all, I would recommend that
| first. You can do filtering (like with an "equalizer") and add
| effects like echo/reverb as linear operations.
|
| I think that it is _particularly_ fun to think of some ground-
| truth signal that is corrupted by an echo in a room and a
| microphone that attenuates some frequencies, and trying to undo
| that corruption.
| chongli wrote:
| You could try making a simple software-rendered 3D game from
| scratch. Basic 3D rendering is pretty much all linear algebra
| computations involving matrices and vectors.
| screye wrote:
| For those interested in these kinds of interractive math
| experiences, I have been keeping track of them for a while. Here
| is my list so far:
|
| * https://www.intmath.com/ - Interactive Mathematics Learn math
| while you play with it
|
| * http://worrydream.com/LadderOfAbstraction/ - up and down the
| ladder of abstraction
|
| * https://betterexplained.com/ - Intuitive guides to various
| things in math
|
| * https://www.math3ma.com/blog/matrices-probability-graphs -
| Viewing Matrices & Probability as Graphs
|
| * http://immersivemath.com/ila/index.html - immersive linear alg
| westurner wrote:
| https://github.com/topics/linear-algebra?l=jupyter+notebook
| lists "Computational Linear Algebra for Coders"
| https://github.com/fastai/numerical-linear-algebra
|
| "site:GitHub.com inurl:awesome linear algebra jupyter" lists a
| few awesome lists with interactive linear algebra resources:
| https://www.google.com/search?q=site%3Agithub.com+inurl%3Aaw...
|
| 3blue1brown's "Essence of linear algebra" playlist has some
| excellent tutorials with intuition-building visualizations
| built with manim:
| https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFit...
|
| https://github.com/ManimCommunity/manim
| TrackerFF wrote:
| I really wish we'd have these kind of tools when I took Linear
| Algebra (or many other math and engineering courses, for that
| mater).
|
| When I took it, it was purely proofs up and down on the
| blackboard, zero visualizations.
| chobytes wrote:
| I think the trouble with LA education is that LA is just so
| ubiquitous and can look very different dependent on context. No
| style is going to suit everyones needs.
| Jtsummers wrote:
| When you took it isn't really the issue as much as where you
| took it. Some schools and college majors choose different ways
| of teaching. I liked my exposure which was over 3 courses: Calc
| 2 had an embedded LA course; a 2xx level computational-focused
| LA course (much expanded version of the 2 or 3 week Calc 2
| version); a 4xx math major only proof-focused LA course.
|
| Most students just needed the brief intro. A substantial
| fraction (but not the majority) got the 2xx computational form.
| A very small number of us took the 4xx version, and since (by
| then) you understood the applications there was little need to
| focus on computations since the interesting (to the course) bit
| was the higher level understanding of LA.
| ChrisArchitect wrote:
| Previous discussion:
|
| _2 years ago_ https://news.ycombinator.com/item?id=21628449
| iainctduncan wrote:
| I am excited to try this, thanks for posting!
| nicomeemes wrote:
| This is one of my favorite resources for learning about Linear
| Algebra. Helped me immensely when I took it last spring.
___________________________________________________________________
(page generated 2021-08-13 23:00 UTC)