Graph Algorithms for Data Science | Hacker News Reader

Graph Algorithms for Data Science

graphs4sci.substack.com

40 pointsAnon8411 comments

When I was studying Reed Solomon the other day, I came across an interesting graph algorithm for error correction codes.

Turns out there are tons of graph ECC out there. Viterbi algorithm is one, and LDPC is another. I don't understand them, but clearly graphs can be used in many obscure situations.

Substack author here. These sound interesting. Can you point me to them? I would be interested in taking a look

I'll try, but as noted earlier, I really don't understand what is going on yet.

http://ipsit.bu.edu/phdthesis_html/node8.html

The above PHd thesis explicitly talks about the Trellis graph constructed for the Vertibi algorithm based Error Correction.

It's complicated, there are matrix representations of these graphs too. It seems like information theorists have many mental models of what is going on, and they just fluidly switch between their mental models without sweating. It makes for a frustrating read, to say the least.

------

Application wise: Vertibi ECC is used for earlier Wifi 802.11... while LDPC is newer like 802.11n or so. Really low level stuff, I'm curious about it but don't really have an application in mind. Just found it curious that it's technically a graph algorithm

Thank you. I’ll check it out

You might have better luck consulting actual textbooks. I don't think what I've found on the internet is very clearly written.

I'm seriously considering buying some textbooks on coding theory, but since this is just idle curiosity... I'm not sure if its worth the effort, lol.

I come from a very different background, so it’s mostly idle curiosity as well. I’ll take a look and if something looks interesting I might dig into it in a post or two

Looking over those PH.D thesis pages... something to note:

* codeword = data * generator_matrix

* codeword * check_matrix = 0_vector

* senseword = codeword + error_vector

* senseword * check_matrix = syndrome_vector

(Yeah, this field likes "horizontal" data vectors. Its weird but you get used to it...)

------

The job of error correction is usually to convert sensewords back into data. Sensewords represent "what the receiver sensed". If no errors occurred, its usually very easy to convert sensewords back into data... but if an error occurred, then you must calculate the syndromes and then figure out a methodology to correct the errors.

Coding schemes set up the matrix in different ways. It seems like Vertibi Algorithm has a graphical representation of the matrix, or something... I still don't understand it but hopefully this post of mine can give you a leg up in understanding what's going on.

I only read marketing here: promises and a need to leave your emailaddress.

True, there isn’t much there yet. It was just launched today, after all.

If you want to check out something a bit more substantive, how about this: https://github.com/DataForScience/Causality

Yeah, it could be very interesting, but without any preview of past issues, or of what kind of message/content I'd receive it's hard to subscribe. Good initiative though, hopefully author is reading this thread and will update it.

I’m the author, and definitely will. Aiming for a 2+ posts a month.

In the GitHub repo above you have links to other blogposts by yours truly

Reply on news.ycombinator.com