Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

String Diagrams for Linear Algebra

graphicallinearalgebra.net

Post reply on HN
Print view View original

11–20 of 27 posts

Re: String Diagrams for Linear Algebra

#11

Post by edflsafoiewq »

Why this episode OP? IMO the proof of fullness is quite belabored. In fact the very next episode gives a much better one-page proof in the section starting "Here’s what we mean by this rather cryptic remark". It's faithfulness that's more interesting, ie. are the graphical rules sufficient to prove that any two diagrams that produce the same outputs given the same inputs are equal, ie. is the list of graphical rules complete?

A string diagram is also equivalent to a program in a generalized-stack language (in the stronger sense of equivalence up to difference in the topological arrangement of the wires, not up to the full graphical rules). Unlike a pure stack language, you can operate on values at any point in the stack, not just the top. The four operations are: drop an element from the stack, push a zero to the stack, remove two elements from the stack and push their sum to the stack, remove an element from the stack and push two copies of it to the stack. Obviously any program in this language computes a linear function of its initial stack (there is a full homomorphism to matrices). A stack language captures the same ability of an input to be consumed that a string diagram does.

Re: String Diagrams for Linear Algebra

#12

Post by colah3 »

Myrmornis wrote: post #6

Is this (closely) related to Penrose tensor notation https://en.wikipedia.org/wiki/Penrose_graphical_notation ?

I expected it to -- graphically, it looks very similar to Penrose notation! -- but at first glance it seems to be quite different.

Penrose notation is very high level: edges correspond to tensor dimensions, joining corresponds roughly to tensor contraction. When you're working with multiple complicated multi-dimensional tensors, it can be a beautiful way to express things.

This notation seems to be expressing something a bit lower level: it seems that edges correspond to values and dots correspond to copy/add. So, roughly, they visually express linear functions. (I didn't read the full post, it's possible that they expand beyond this initial meaning.) Diagrams of a similar style are used in other contexts (eg. expressing the weights of neural networks), often as a pedagogical tool.

Re: String Diagrams for Linear Algebra

#16

Post by edflsafoiewq »

saroyas wrote: post #2

Matrices, although great for computers, are often complicated and unintuitive. This blog was my first insight into an alternative symbolic interpretation for Linear Algebra. It has often led to problems and complicated equations being represented with far more simplicity. As well as teaching me to be more flexible and creative with my own notations.

> It has often led to problems and complicated equations being represented with far more simplicity.

How? AFAICT, the string diagram contains far too much incidental information for doing linear algebra. It contains even more information that a fully parenthesized tree of additions because it even contains information about how to evaluate duplicated expressions (eg. it tells if in (x+y)+(x+y) you should evaluate (x+y) twice or only once and then reuse the value). If we write a string diagram as a normal linear system the whole question of fullness and faithfulness would be dead obvious.

Re: String Diagrams for Linear Algebra

#17

Post by mathgenius »

Myrmornis wrote: post #6

Is this (closely) related to Penrose tensor notation https://en.wikipedia.org/wiki/Penrose_graphical_notation ?

It might be easier to think of it as a kind of Feynman diagram: a sum over paths. That's what matrix multiplication is, it's a kind of sum over weighted paths. A matrix records all the ways to get from the set of "columns" to the set of "rows".

Re: String Diagrams for Linear Algebra

#19

Post by carapace »

edflsafoiewq wrote: post #11

Why this episode OP? IMO the proof of fullness is quite belabored. In fact the very next episode gives a much better one-page proof in the section starting "Here’s what we mean by this rather cryptic remark". It's faithfulness that's more interesting, ie. are the graphical rules sufficient to prove that any two diagrams that produce the same outputs given the same inputs are equal, ie. is the list of graphical rules…

> Unlike a pure stack language, you can operate on values at any point in the stack, not just the top.

There's a language, Joy, that has combinators that allow you to work deeper in the stack, e.g. "dip":

       a b c [F] dip
    -------------------
          a b F c


    dipd == [dip] cons dip


    a b c [F] dipd
    a b c [F] [dip] cons dip
    a b c [[F] dip]      dip
    a b    [F] dip c
    a       F    b c
And so on...

I think it's a "Category Theory" paradigm language, whatever that might mean.

Joy resembles the point-free form of Haskell from Conal Elliott's "Compiling to categories" http://conal.net/papers/compiling-to-categories/ )

Post reply on HN