Linear Regression - least squares with orthogonal projection

Compared to the previous article where we simply used vector derivatives we’ll now try to derive the formula for least squares simply by the properties of linear transformations and the four fundamental subspaces of linear algebra. These are: Kernel $Ker(A)$: The set of all solutions to $Ax = 0$. Sometimes we can say nullspace $N(A)$ instead of kernel. Image $Im(A)$: The set of all right sides $b$, for which there is a solution $Ax = b$.

Read More →

Matrix Inversion Lemma

This article is a draft and as such there might be typos and other inaccuracies. In this article we’ll derive the matrix inversion lemma, also known as the Sherman-Morrisson-Woodbury formula. At first it might seem like a very boring piece of linear algebra, but it has a few nifty uses, as we’ll see in one of the followup articles. Let’s start with the following block matrix: $$ M = \begin{bmatrix} A & U \\\

Read More →

Linear Regression - Least Squares Without Orthogonal Projection

There are multiple ways one can arrive at the least squares solution to linear regression. I’ve always seen the one using orthogonality, but there is another way which I’d say is even simpler, especially if you’ve done any calculus. Let’s define the problem first. Given a matrix \(N \times M\) matrix \(X\) of inputs, and a vector \(y\) of length \(N\) containing the outputs, the goal is to find a weight vector \(w\) of length \(M\) such that:

Read More →

Let’s Write a 2D Platformer From Scratch Using HTML5 and JavaScript, Part 1: Game Loop

As far as gamedev and HTML5 goes, there are tons of great game engines already out there. How do we pick the right one? Look at the number of stars on GitHub? The number of contributors? The number of published games? If you've looked at the previous articles on this blog, you probably know where this is heading (or read the title for that matter). We're going to write our own game engine first!

Read More →

Binary Search in JavaScript

Binary search is an extremely useful and popular algorithm used for quickly searching in a sorted array. Binary search is even used by people in real life (outside of programming) when they play the guess the number game. One person thinks a number between 1 and 100, and the other person tries to guess. The response is only less, equal or greater. If you guess 50 and get a _less_ response, you just narrowed down the search to half the interval, 1 to 50. You can keep going and guess 25. No matter if what answer you get, you either win, or narrow down the interval again to a half. This is how binary search works.

Read More →

Binary Heap (Priority Queue) in JavaScript

A binary heap is a simple data structure most often used for implementing priority queues. In a more general sense, a *heap* is a tree-based data structure which satisfies the *heap property*, and a *binary heap* is a *heap* which uses a *binary tree* to store its data. Any arbitrary binary tree which satisfies the following two properties can be considered a binary heap.

Read More →

Few notes on the Binomial and Fibonacci heaps

Having just implemented and tested a Fibonacci heap on a large dataset I thought I’d write up a bit about it, mostly so that I can reference this post later in the future, and to help me remember things I’ve learned better. Note that this blog post is not a tutorial on how to implement a Binomial/Fibonacci heap. First, let’s begin with a few definitions. Throughout the article we’ll be talking about min-heaps.

Read More →

Bloom filter in JavaScript

A Bloom filter is a simple yet powerful data structure. It allows you to answer the question have you seen this before? in a very fast and memory efficient way. Unlike a regular set, a Bloom filter only needs to store a few bits per item instead of storing the whole thing.

Read More →