{"id":2093,"date":"2025-06-07T01:56:10","date_gmt":"2025-06-07T01:56:10","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=2093"},"modified":"2025-06-07T18:02:42","modified_gmt":"2025-06-07T18:02:42","slug":"a-neat-not-randomized-algorithm-the-polar-express","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2025\/06\/07\/a-neat-not-randomized-algorithm-the-polar-express\/","title":{"rendered":"A Neat Not-Randomized Algorithm: Polar Express"},"content":{"rendered":"\n

Every once in a while, there’s a paper that comes out that is so delightful that I can’t help share it on this blog, and I’ve started a little series Neat Randomized Algorithms<\/a><\/em> for exactly this purpose. Today’s entry into this collection is The Polar Express: Optimal Matrix Sign Methods and their Application to the Muon Algorithm<\/a><\/em> by Noah Amsel<\/a>, David Persson<\/a>, Christopher Musco<\/a>, and Robert M. Gower<\/a>. Despite its authors belonging to the randomized linear algebra ouvr\u00e9, this paper is actually about a plain-old deterministic algorithm. But it’s just so delightful that I couldn’t help but share it in this series any way.<\/p>\n\n\n\n

The authors of The Polar Express<\/em> are motivated by the recent Muon algorithm<\/a> for neural network optimization. The basic idea of Muon is that it helps to orthogonalize<\/em> the search directions in a stochastic gradient method. That is, rather than update a weight matrix \"W\" with search direction \"G\" using the update rule

  <\/span>   <\/span>\"\[W \gets W - \eta G,\]\"<\/p>instead use the update

  <\/span>   <\/span>\"\[W\gets W - \eta \operatorname{polar}(G).\]\"<\/p>Here,

  <\/span>   <\/span>\"\[\operatorname{polar}(G) \coloneqq \operatorname*{argmin}_{Q \textrm{ with orthonormal columns}} \norm{G - Q}_{\rm F}\]\"<\/p>is the closed matrix with orthonormal columns to \"G\" and is called the (unitary) polar factor<\/a><\/em> of \"G\". (Throughout this post, we shall assume for simplicity that \"G\" is tall and full-rank<\/mark><\/em>.) Muon relies on efficient algorithms for rapidly approximating \"\operatorname{polar}(G)\".<\/p>\n\n\n\n

Given a singular value decomposition \"G = U\Sigma V^\top\", the polar factor may be computed in closed form as \"\operatorname{polar}(G) = UV^\top\". But computing the SVD is computationally expensive, particularly in GPU computing environments. Are there more efficient algorithms that avoid the SVD? In particular, can we design algorithms that use only matrix multiplications, for maximum GPU efficiency?<\/p>\n\n\n\n

The Polar Factor as a Singular Value Transformation<\/h2>\n\n\n\n

Computing the polar factor \"\operatorname{polar}(G)\" of a matrix \"G\" effectively applies an operation to \"G\" which replaces all of its singular values by one. Such operations are studied in quantum computing<\/a>, where they are called singular value transformations.<\/p>\n\n\n\n

Definition (singular value transformation):<\/strong> Given an odd<\/mark><\/em> function \"f\", the singular value transformation of \"G = U\Sigma V^\top\" by \"f\" is \"f[G] \coloneqq Uf(\Sigma)V^\top\".<\/p>\n\n\n\n

On its face, it might seem like that the polar factor of \"G\" is cannot be obtained as a singular value transformation. After all, the constantly one function \"f(x)= 1\" is not odd. But, to obtain the polar factor, we only need a function \"f\" which sends positive inputs<\/em> to \"1\". Thus, the polar decomposition \"\operatorname{polar}(G)\" is given by the singular value transformation associated with the sign function<\/em>:

  <\/span>   <\/span>\"\[\operatorname{sign}(x) = \begin{cases} 1, & x > 0, \\ 0, & x = 0, \\ -1, & x < 0. \end{cases}\]\"<\/p>The sign function is manifestly odd, and the polar factor satisfies <\/p>\n\n\n\n

  <\/span>   <\/span>\"\[\operatorname{polar}(G) = \operatorname{sign}[G].\]\"<\/p><\/p>\n\n\n\n

Singular Value Transformations and Polynomials<\/h2>\n\n\n\n

How might we go about computing the singular value transformation of a matrix? For an (odd) polynomial, this computation can be accomplished using a sequence of matrix multiplications alone. Indeed, for \"p(x) = a_1 x + a_3 x^3 + \cdots + a_{2k+1} x^{2k+1}\", we have

  <\/span>   <\/span>\"\[p[G] = a_1 G + a_3 G(G^\top G) + \cdots + a_{2k+1} G(G^\top G)^k.\]\"<\/p>For a general (odd) function \"f\", we can approximately compute the singular value transformation \"f[G]\" by first approximating \"f\" by a polynomial \"p\", and then using \"p[G]\" as a proxy for \"f[G]\". Here is an example:<\/p>\n\n\n\n

>> G = randn(2)                            % Random test matrix<\/mark>\nG =\n   0.979389080992349  -0.198317114406418\n  -0.252310961830649  -1.242378171072736\n>> [U,S,V] = svd(G);\n>> fG = U*sin(S)*V'                        % Singular value transformation<\/mark>\nfG =\n   0.824317193982434  -0.167053523352195\n  -0.189850719961322  -0.935356030417109\n>> pG = G - (G*G'*G)\/6 + (G*G'*G*G'*G)\/120 % Polynomial approximation<\/mark>\npG =\n   0.824508188218982  -0.167091255945116\n  -0.190054681059327  -0.936356677704568<\/code><\/pre>\n\n\n\n
We see that we get reasonably high accuracy by approximating \"\sin[G]\" using its degree-three Taylor polynomial.<\/p>\n\n\n\n
The Power of Composition<\/h2>\n\n\n\n
The most basic approach to computing the sign function would be to use a fixed polynomial of degree \"2k+1\". However, this approach converges fairly slowly as we increase the degree \"k\".<\/p>\n\n\n\n
A better strategy is to use compositions. A nice feature of the sign function is the fixed point property:<\/em> For every \"x\", \"\operatorname{sign}(x)\" is a fixed point of the \"\operatorname{sign}\" function: 
   <\/span>   <\/span>\"\[\operatorname{sign}(\operatorname{sign}(x)) = \operatorname{sign}(x) \quad \text{for all } x \in \real.\]\"<\/p>The fixed point strategy suggests an alternate strategy for computing the sign function using polynomials. Rather than using one polynomial of large degree, we can instead compose many polynomials of low degree. The simplest such compositional algorithm is the Newton\u2013Schulz iteration<\/em>, which consists of initializing \"P\gets G\" applying the following fixed point equation until convergence: 
   <\/span>   <\/span>\"\[P \gets \frac{3}{2} P - \frac{1}{2} PP^\top P.\]\"<\/p>Here is an example execution of the algorithm:<\/p>\n\n\n\n
>> P = randn(100) \/ 25;\n>> [U,~,V] = svd(P); polar = U*V'; % True polar decomposition<\/mark>\n>> for i = 1:20\n      P = 1.5*P-0.5*P*P'*P; % Newton-Schulz iteration<\/mark>\n      fprintf(\"Iteration %d\\terror %e\\n\",i,norm(P - polar));\n   end\nIteration 1\terror 9.961421e-01\nIteration 2\terror 9.942132e-01\nIteration 3\terror 9.913198e-01\nIteration 4\terror 9.869801e-01\nIteration 5\terror 9.804712e-01\nIteration 6\terror 9.707106e-01\nIteration 7\terror 9.560784e-01\nIteration 8\terror 9.341600e-01\nIteration 9\terror 9.013827e-01\nIteration 10\terror 8.525536e-01\nIteration 11\terror 7.804331e-01\nIteration 12\terror 6.759423e-01\nIteration 13\terror 5.309287e-01\nIteration 14\terror 3.479974e-01\nIteration 15\terror 1.605817e-01\nIteration 16\terror 3.660929e-02\nIteration 17\terror 1.985827e-03\nIteration 18\terror 5.911348e-06\nIteration 19\terror 5.241446e-11\nIteration 20\terror 6.686995e-15<\/mark><\/code><\/pre>\n\n\n\n
As we see, the initial rate of convergence is very slow, and obtain only a single digit of accuracy after 15 iterations. After this burn-in period, the rate of convergence is very rapid, and the method achieves machine accuracy after 20 iterations.<\/p>\n\n\n\n
The Polar Express<\/h2>\n\n\n\n
The Newton\u2013Schulz iteration approximates the sign function using a composition of the same polynomial \"p\" repeatedly. But we can get better approximations by applying a sequence of different<\/em> polynomials \"p_1,\ldots,p_t\", resulting in an approximation of the form 
   <\/span>   <\/span>\"\[\operatorname{sign}[G] \approx p_t[p_{t-1}[\cdots[p_2[p_1[G]]\cdots]].\]\"<\/p>The Polar Express<\/em> paper asks the question:<\/p>\n\n\n\n
\n
What are the optimal<\/em> choice of polynomials \"p_i\"?<\/p>\n<\/blockquote>\n\n\n\n
For simplicity, the authors of The Polar Express<\/em> focus on the case where all of the polynomials \"p_i\" have the same (odd) degree \"2k+1\".<\/p>\n\n\n\n
On its face, it seems like this problem might be intractable as the best choice of polynomial \"p_{i+1}\" seemly could depend in a complicated way on all of the previous polynomials \"p_1,\ldots,p_i\". Fortunately, the authors of The Polar Express<\/em> show that there is a very simple way of computing the optimal polynomials. Begin by assuming that the singular values of \"G\" lie in an interval \"[\ell_0,u_0]\". We then choose \"p_1\" to be the degree-(\"2k+1\") odd polynomial approximation to the sign function on \"[\ell_0,u_0]\" that minimizes the \"L_\infty\" error:
   <\/span>   <\/span>\"\[p_1 = \operatorname*{argmin}_{\text{odd degree-($2k+1$) polynomial } p} \max_{x \in [\ell_0,u_0]} |p(x) - \operatorname{sign}(x)|.\]\"<\/p>This optimal polynomial can be computed by a version of the Remez algorithm<\/a> provided in the Polar Express paper. After applying \"p_1\" to \"G\", the singular values of \"p_1[G]\" lie in a new interval \"[\ell_1,u_1]\". To build the next polynomial \"p_2\", we simply find the optimal approximation to the sign function on this interval: 
   <\/span>   <\/span>\"\[p_2 = \operatorname*{argmin}_{\text{odd degree-($2k+1$) polynomial } p} \max_{x \in [\ell_1,u_1]} |p(x) - \operatorname{sign}(x)|.\]\"<\/p>Continuing in this way, we can generate as many polynomials \"p_1,p_2,\ldots\" as we want. <\/p>\n\n\n\n
For given values of \"\ell_0\" and \"u_0\", the coefficients of the optimal polynomials \"p_1,p_2,\ldots\" can be computed in advance and stored, allowing for rapid deployment at runtime. Moreover, we can always ensure the upper bound is \"u_0 = 1\" by normalizing \"G\gets G / \norm{G}_{\rm F}\". As such, there is only one parameter \"\ell_0\" that we need to know in order to compute the optimal coefficients. The authors of The Polar Express<\/em> are motivated by applications in deep learning using 16-bit floating point numbers. In this value, the lower bound \"\ell_0 = 0.001\" is appropriate. (As the authors stress, their method remains convergent even if too large a value of \"\ell_0\" is chosen, though convergence may be slowed somewhat.)<\/p>\n\n\n\n
Below, I repeat the experiment from above using (degree-5) Polar Express<\/em> instead of Newton\u2013Schulz. The coefficients for the optimal polynomials are taken from the Polar Express paper. <\/p>\n\n\n\n
>> P = randn(100) \/ 25;\n>> [U,~,V] = svd(P); polar = U*V';\n>> P2 = P*P'; P = ((17.300387312530933*P2-23.595886519098837*eye(100))*P2+8.28721201814563*eye(100))*P; fprintf(\"Iteration 1\\terror %e\\n\",norm(P - polar));\nIteration 1\terror 9.921347e-01<\/mark>\n>> P2 = P*P'; P = ((0.5448431082926601*P2-2.9478499167379106*eye(100))*P2+4.107059111542203*eye(100))*P; fprintf(\"Iteration 2\\terror %e\\n\",norm(P - polar));\nIteration 2\terror 9.676980e-01<\/mark>\n>> P2 = P*P'; P = ((0.5518191394370137*P2-2.908902115962949*eye(100))*P2+3.9486908534822946*eye(100))*P; fprintf(\"Iteration 3\\terror %e\\n\",norm(P - polar));\nIteration 3\terror 8.725474e-01<\/mark>\n>> P2 = P*P'; P = ((0.51004894012372*P2-2.488488024314874*eye(100))*P2+3.3184196573706015*eye(100))*P; fprintf(\"Iteration 4\\terror %e\\n\",norm(P - polar));\nIteration 4\terror 5.821937e-01<\/mark>\n>> P2 = P*P'; P = ((0.4188073119525673*P2-1.6689039845747493*eye(100))*P2+2.300652019954817*eye(100))*P; fprintf(\"Iteration 5\\terror %e\\n\",norm(P - polar));\nIteration 5\terror 1.551595e-01<\/mark>\n>> P2 = P*P'; P = ((0.37680408948524835*P2-1.2679958271945868*eye(100))*P2+1.891301407787398*eye(100))*P; fprintf(\"Iteration 6\\terror %e\\n\",norm(P - polar));\nIteration 6\terror 4.588549e-03<\/mark>\n>> P2 = P*P'; P = ((0.3750001645474248*P2-1.2500016453999487*eye(100))*P2+1.8750014808534479*eye(100))*P; fprintf(\"Iteration 7\\terror %e\\n\",norm(P - polar));\nIteration 7\terror 2.286853e-07<\/mark>\n>> P2 = P*P'; P = ((0.375*P2-1.25*eye(100))*P2+1.875*eye(100))*P; fprintf(\"Iteration 8\\terror %e\\n\",norm(P - polar));\nIteration 8\terror 1.113148e-14<\/mark><\/code><\/pre>\n\n\n\n
We see that the Polar Express algorithm converges to machine accuracy in only 8 iterations (24 matrix products), a speedup over the 20 iterations (40 matrix products) required by Newton\u2013Schulz. The Polar Express paper contains further examples with even more significant speedups.<\/p>\n\n\n\n
Make sure to check out the Polar Express paper for many details not shared here, including extra tricks to improve stability in 16-bit floating point arithmetic, discussions about how to compute the optimal polynomials, and demonstrations of the Polar Express algorithm for training GPT-2.<\/p>\n\n\n\n
Every once in a while, there’s a paper that comes out that is so delightful that I can’t help share it on this blog, and I’ve started a little series Neat Randomized Algorithms for exactly this purpose. Today’s entry into this collection is The Polar Express: Optimal Matrix Sign Methods and their Application to theRead more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[15],"tags":[],"class_list":["post-2093","post","type-post","status-publish","format-standard","hentry","category-neat-randomized-algorithms"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2093","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/comments?post=2093"}],"version-history":[{"count":27,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2093\/revisions"}],"predecessor-version":[{"id":2122,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2093\/revisions\/2122"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=2093"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=2093"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=2093"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
References:<\/strong> Muon was first formally described in the blog post Muon: An optimizer for hidden layers in neural networks<\/a><\/em> (2024); for more, see this blog post<\/a> by Jeremy Bernstein<\/a> and this paper<\/a> by Jeremy Bernstein and Laker Newhouse<\/a>. The Polar Express is proposed in The Polar Express: Optimal Matrix Sign Methods and their Application to the Muon Algorithm<\/a><\/em> (2025) by Noah Amsel<\/a>, David Persson<\/a>, Christopher Musco<\/a>, and Robert M. Gower<\/a>. For more on the matrix sign function and computing it, chapter 5 of Functions of Matrices: Theory and Computation<\/a><\/em> (2008) by Nicholas H. Higham<\/a> is an enduringly useful reference. <\/p>\n","protected":false},"excerpt":{"rendered":"