NOTE: This post was originally written in 2011 so it may be dated. I’m resurrecting it due to relative popularity. This post has been copied between several blogging systems (some of which were home-brewed) and some formatting has been lost along the way.
Before some recent machine learning implementations in node I set out to find
a reasonable matrix math/linear algebra library for node.js. The pickings were
slim but I managed to dig up a general JavaScript matrix math library written
by James Coglan called sylvester. Clearly, sylvester had to be node-ified.
With the help of Rob Ellis (a collaborator on natural) it’s been wrapped up into
a node project titled node-sylvester & NPM and has had some features added such as element-wise multiplication,
QR, LU, SVD decompositions and basic solving of systems of linear equations.
In this post I’ll cover some of the basic structures and operations supported by
sylvester, but it will by no means be complete. I’ll focus solely on the Matrix
and Vector prototypes, but sylvester also supports Line, Plane,
and Polygon. Also within the covered prototypes I’ll only
demonstrate a small, but useful subset of their functionality.
Currently, the only reasonable sources of documentation for functionality
existing only in the node port are in the README while general sylvester
functionality is covered in its API docs. In time I will (hopefully with the
help of the community) provide some more complete documentation.
Installation
Getting ready to use the node port of sylvester is what you’d expect, a standard
NPM install.
npm install sylvesterYou can then require-up sylvester in your node code and use the prototypes
within.
var sylvester = require('sylvester'),
Matrix = sylvester.Matrix,
Vector = sylvester.Vector;
Vector and Matrix Prototypes
Matrices and vectors are abstracted by the Matrix and Vector prototypes.
Instances can be created using their create functions and passing in an array of values. Vector.create accepts a one dimensional array of numbers and Matrix.create accepts multiple dimensions.
var x = Vector.create([1, 2, 3]);
var a = Matrix.create([[1, 2], [3, 4]]);
representing:
Global shortcuts exist to clone Vector and Matrix prototypes with $V and $M
respectively. The following is the semantic equivalent of the previous example.
var x = $V([1, 2, 3]);
var a = $M([[1, 2], [3, 4]]);
Matrix‘s Ones function will create a matrix of specified dimensions with all
elements set to 1.
var ones = Matrix.Ones(3, 2);
Matrix‘s Zeros function does the same except with all elements set to 0.
var zeros = Matrix.Zeros(3, 2);
An identity matrix of a given size can be created with Matrix‘s I function.
var eye = Matrix.I(4);
Data Access
Values can be retrieved from within a Matrix or Vector using the e method.
a.e(2, 1); // returns 3
x.e(3); // returns 3
The entire set of values can be retrieved/manipulated with the elements member of Matrix and Vector. elements is an array-of-arrays-of-numbers in the case of matrices and it is a simple array-of-numbers for vectors.
var a_elements = a.elements; // [[1, 2], [3, 4]]
var x_elements = x.elements; // [1, 2, 3]
Basic Math
Many standard mathematic operations are supported in Vector and Matrix clones. In general the arguments can either be scalar values or properly-dimensioned Matrix/Vector clones. While not covered here element-wise versions of many multiplicative/specialized operations are also available.
Matrices and vectors can be added-to and subtracted-from by scalar values using
the add and subtract functions.
var b = a.add(1);
var d = a.subtract(1);
symbolizing:
Naturally, like-dimensioned matrices and vectors can be added to and subtracted from each other.
var e = a.add($M([[2, 3], [4, 5]]));
var f = a.subtract($M([[0, 2], [3, 3]]));
meaning:
Matrices/vectors can be multiplied with matrices/vectors of
appropriate dimensions.
var g = a.x($V([3, 4]));
The dot-product of two vectors can be computed with Vector‘s dot method.
var y = x.dot($V([4, 5, 6]));
depicting:
Transposing
A Matrix can be transposed with the transpose method.
var at = a.transpose();
where at represents the matrix:
Segmentation/Augmentation
The first n elements can be removed from a Vector with the chomp method.
var n = 2;
var xa = x.chomp(n);
In contrast the first n elements can be retrieved with the top method.
var xb = x.top(n);
Vectors can have a list of values appended to the end with the augment method.
var xc = x.augment([4, 5]);
Matrices can have a column appended to the right with Matrix‘s augment method.
var m = a.augment($V([3, 5]));
A sub-block of a Matrix clone can be retrieved with the slice method. slice
accepts a starting row, ending row, starting column and ending column as
parameters.
var aa = $M([[1, 2, 3], [4, 5, 6], [7, 8, 9]]);
var ab = aa.slice(1, 2, 1, 2);
The code above produces a matrix ab shaped like:
Decompositions/Advanced functions
A small number of decompositions are currently supported. These have all been
recently added and at the time of writing are, while functional, not
necessarily as computationally efficient as they could be. Also their stability cannot be guaranteed at this time.
Note that these were all implemented in pure JavaScript. My personal hope is to
keep node-sylvester 100% functional in pure JavaScript to maintain the best
compatibility across all platforms. In the long run, however, I hope to employ
time-tested, computationally-efficient native libraries to perform these
operations if the host machine allows.
A QR decomposition is made possible via Matrix‘s qr method. An object is
returned containing both the Q and the R matrix.
var qr = a.qr();
resulting in the object:
{ Q:
[-0.316227766016838, -0.9486832980505138]
[-0.9486832980505138, 0.3162277660168381],
R:
[-3.162277660168379, -4.427188724235731]
[5.551115123125783e-16, -0.6324555320336751] }
Singular Value Decompositions (SVD) can be produced via Matrix‘s aptly named svd
method. An object is returned containing the U (left singular), S (singular
diagonal), and V (right singular) matrices.
var svd = a.svd();
which returns:
{ U:
[0.40455358483359943, 0.9145142956773742]
[0.9145142956773744, -0.40455358483359943],
S:
[5.4649857042190435, 0]
[0, 0.36596619062625785],
V:
[0.5760484367663301, -0.8174155604703566]
[0.8174155604703568, 0.5760484367663302] }
Principal Component Analysis can be performed (dimensionality reduced) and
reversed (dimensionality restored with approximated values) using Matrix‘s
pcaProject and pcaRecover methods respectively.
pcaProject accepts the number of target dimensions as a parameter and returns
an object with the reduced data Z and the covariant eigenvectors U.
var pca = a.pcaProject(1);
{ Z:
[2.2108795577070475]
[4.997807552180416],
U:
[0.5760484367663208, -0.8174155604703633]
[0.8174155604703633, 0.5760484367663208] }
and pcaRecover approximately recovers the data to the original dimensionality.
pca.Z.pcaRecover(pca.U);
which produces:
Solving Linear Equations
Simple linear equations in the form of
can be solved using the suitability-named solve method.
var A = $M([
[2, 4],
[2, 3],
]);
var b = $V([2, 2]);
var x= M.solve(b);
which is representative of
Conclusion
Thanks to James Coglan’s hard work on sylvester plenty of matrix math
functionality has been exposed to JavaScript. With a little extra work we’ve
been able to expose quite a bit more to node. There’s still more work to do
not only in optimization but also in capabilities. In time hopefully
node-sylvester will become fast and complete.
As a reminder, the functionality outlined above is not representative of the
full list of current capabilities. Between the README in the source and the
sylvester API documentation you should be able to get a reasonably clear
picture. Still, if you’re looking for ways to help with the project a concerted
documentation effort would be wonderful and appreciated.