{"id":4906,"date":"2025-10-28T21:25:44","date_gmt":"2025-10-28T21:25:44","guid":{"rendered":"https:\/\/sinatootoonian.com\/?p=4906"},"modified":"2025-12-27T15:53:47","modified_gmt":"2025-12-27T15:53:47","slug":"the-low-rank-hypothesis-of-complex-systems","status":"publish","type":"post","link":"https:\/\/sinatootoonian.com\/index.php\/2025\/10\/28\/the-low-rank-hypothesis-of-complex-systems\/","title":{"rendered":"The low-rank hypothesis of complex systems"},"content":{"rendered":"\n<p>In this post I will summarize the paper &#8220;<a href=\"https:\/\/www.nature.com\/articles\/s41567-023-02303-0\">The low-rank hypothesis of complex systems<\/a>&#8221; by Thibeault et al.<\/p>\n\n\n\n<p>The authors appear to be coming from the complex-systems \/ network science. Their argument is as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Many real world networks have low rank interaction matrices.<\/li>\n\n\n\n<li>Several important random matrix models are an element-wise function of a low rank matrix, plus noise, and remain low-rank.<\/li>\n\n\n\n<li>Low rank interactions suggests low-dimensional dynamics.<\/li>\n\n\n\n<li>These are found by aligning a to-be-determined low-dimensional vector field with some aspect of the high-dimensional one.<\/li>\n\n\n\n<li>The most natural way to do this is complicated.<\/li>\n\n\n\n<li>Solving a related problem they arrive at $F^*(X) = M f(M^\\dagger,X)$ for projection matrix $M$.<\/li>\n\n\n\n<li>Use this to show how the error is bounded by the singular values.<\/li>\n\n\n\n<li>When the projection is aligned with the connectivity matrix $W$, the low-dimensional projection can exactly capture the high-dimensional one in some important cases, including RNNs.<\/li>\n\n\n\n<li>Their ansatz also implies higher-order interactions of the low-dimensional observables.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Many real world networks have low effective rank<\/h2>\n\n\n\n<p>Many complex systems consist of a large number of interacting units. The interactions of these units can often be described by a matrix W indicating the influence of each unit on every other. This is schematized below.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"627\" height=\"487\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image.png\" alt=\"\" class=\"wp-image-4908\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image.png 627w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-300x233.png 300w\" sizes=\"auto, (max-width: 627px) 100vw, 627px\" \/><\/figure>\n\n\n\n<p>The interactions defined by W can be complex. This complexity can be measured by the singular values of W, specifically by how quickly they decay. The singular values determine the best-low rank approximation of W. <\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"175\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-1-1024x175.png\" alt=\"\" class=\"wp-image-4909\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-1-1024x175.png 1024w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-1-300x51.png 300w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-1-768x131.png 768w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-1-1536x263.png 1536w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-1.png 1742w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Therefore, the faster the singular values decay the more structured it is. The rapidity of decay can be quantified into various measures of effective rank. For example, the <em>stable rank<\/em> measures the cumulative sum of squares of the singular values normalized by the largest. The decay of the singular values, along with various measures of effective rank, computed for the connectome above, are shown below.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"306\" height=\"318\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-2.png\" alt=\"\" class=\"wp-image-4910\" style=\"width:462px;height:auto\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-2.png 306w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-2-289x300.png 289w\" sizes=\"auto, (max-width: 306px) 100vw, 306px\" \/><\/figure>\n\n\n\n<p>It turns out that many real-world networks have low effective rank. The authors examined ~700 such networks and computed the statistics of singular value decay, shown below:<br><\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"663\" height=\"723\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-3.png\" alt=\"\" class=\"wp-image-4913\" style=\"width:570px;height:auto\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-3.png 663w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-3-275x300.png 275w\" sizes=\"auto, (max-width: 663px) 100vw, 663px\" \/><\/figure>\n\n\n\n<p>The stable rank of these is typically 10% or less of the ambient rank.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"642\" height=\"653\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-4.png\" alt=\"\" class=\"wp-image-4914\" style=\"width:635px;height:auto\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-4.png 642w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-4-295x300.png 295w\" sizes=\"auto, (max-width: 642px) 100vw, 642px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Many random graphs are built atop low-rank matrices<\/h2>\n\n\n\n<p>Many random graph models can be decomposed as an element wise function of a low rank matrix, corrupted by additive noise.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"280\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-5-1024x280.png\" alt=\"\" class=\"wp-image-4917\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-5-1024x280.png 1024w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-5-300x82.png 300w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-5-768x210.png 768w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-5.png 1189w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Despite the element-wise function and the additive noise, the resulting weight matrices retain their low-ranked-ness, partially due to Weyl&#8217;s theorem showing that singular values are robust to additive perturbations.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"351\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-6-1024x351.png\" alt=\"\" class=\"wp-image-4918\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-6-1024x351.png 1024w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-6-300x103.png 300w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-6-768x263.png 768w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-6.png 1382w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">The low-dimension hypothesis<\/h2>\n\n\n\n<p>Low rank structure in the interactions among units suggests that the dynamics of such a system may have low dimensional structure. Specifically, we hope to find a low-dimensional linear projection of the activity, defined by the $n \\times N$ matrix $M$, that matches the high-dimensional dynamics. That is, given dynamics $$\\dot x = f(x),$$ we hope to find $X \\triangleq M x$ whose dynamics $$\\dot X = F(X)$$ match the original in some least squares sense.<\/p>\n\n\n\n<p>One natural way to do this is to project the complete dynamics and compare them to the reduced dynamics, $$ \\mathcal{E}(x) = \\|M f(x) &#8211; F(M x)\\|.$$ This is shown schematically below.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"683\" height=\"1024\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-7-683x1024.png\" alt=\"\" class=\"wp-image-4936\" style=\"width:405px;height:auto\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-7-683x1024.png 683w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-7-200x300.png 200w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-7-768x1152.png 768w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-7.png 904w\" sizes=\"auto, (max-width: 683px) 100vw, 683px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">A dimension reduction ansatz<\/h2>\n\n\n\n<p>However, minimizing this over $M$ and $F$ is hard. Instead, we consider lifting the low-dimensional dynamics to the complete space using the pseudo-inverse $M^\\dagger$ of the projection and comparing it to the complete dynamics on the projection, so $$ \\veps(x) = \\|f(Px) &#8211; M^\\dagger F(M x)\\|,$$ where $P = M^\\dagger M$ is the projection from $\\RR^n \\to \\RR^N$. It turns out that this has a simple solution. Since $$f(Px) = f(M^\\dagger M x) = f(M^\\dagger X),$$ we can write the above error as $$ \\veps(x) = \\|f(M^\\dagger X) &#8211; M^\\dagger F(X)\\|.$$ So we just set $$ F^*(X) = M f (M^\\dagger X).$$<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Bounding the reconstruction error<\/h3>\n\n\n\n<p>We can now bound the error we&#8217;re interested in for this particular choice of vector field. Before doing so, we make one more assumption to make the dependence on the structure expliction, that the dynamics are of the form $$ f(x) = g(x, y), \\quad y = W x.$$ Defining the projections $$\\hat x \\triangleq M x, \\quad \\text{and} \\quad \\hat y \\triangleq M y,$$ our error is $$ \\mathcal{E}(x) = \\|M g(x,y) &#8211; M g(\\tilde x, \\tilde y)\\| = \\| M [g(x,y) &#8211; g(\\tilde x, \\tilde y)] \\|.$$  <\/p>\n\n\n\n<p>The difference in the vector fields can be described using the jacobians of g as $$ g(x,y) &#8211; g(\\tilde x, \\tilde y) = J_x (x &#8211; \\tilde x) + J_y (y &#8211; \\tilde y) = J_x (x &#8211; \\tilde x) + J_ y W (x &#8211; \\tilde x),$$ where the Jacobians are evaluated at some intermediate point between $\\tilde x$ and $x,$ and $\\tilde y$ and $y.$ Also, $$x &#8211; \\tilde x = x_\\perp =  (I &#8211; P) x, \\quad P = M^\\dagger M.$$ So our error becomes $$ \\mathcal{E}(x) = \\|M g(x,y) &#8211; M g(\\tilde x, \\tilde y)\\| = \\| M J_x (I &#8211; P) x + M J_y W (I &#8211; P) x \\|.$$<\/p>\n\n\n\n<p>We can use the triangle inequality to split this up into two components,$$ \\mathcal{E}(x) \\le  \\| M J_x x_\\perp\\| + \\|M J_y W x_\\perp \\|.$$<\/p>\n\n\n\n<p>To bring $W$ further into the picture, we split the second component further, so $$ \\mathcal{E}(x) \\le  \\| M J_x x_\\perp\\| + \\|M J_y\\| \\| W x_\\perp \\|.$$<\/p>\n\n\n\n<p>Now if we set $M = V_n^T$, the first $n$ singular vectors of $W$, then we can bound the last term, so $$ \\mathcal{E}(x) \\le  \\| M J_x x_\\perp\\| + \\sigma_{n+1} \\|M J_y\\|   \\|x_\\perp\\|.$$<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Exact reconstruction<\/h4>\n\n\n\n<p>From this, we get that if $J_x \\propto I$, the first term is zero, and $n = \\text{rank}(W)$ makes the second term zero. So our ansatz vector field gives <strong>exact reconstruction <\/strong>in those cases. An important example of this is for RNNs, with dynamics like $$ \\dot x = -x + s(W x),$$ for $W = U S V^T$ of rank $n$ and some fixed function $s$ that can include inputs to each unit. Our ansatz says that this can by exactly dimension reduced using $$ \\dot X = -X + V^T s( U \\Sigma X), \\quad X = V^T x.$$ An example of this is shown below. The black data is the bound, the blue data are the singular values of $W$, and the reconstruction error is in red.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"628\" height=\"651\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-8.png\" alt=\"\" class=\"wp-image-4961\" style=\"width:397px;height:auto\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-8.png 628w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-8-289x300.png 289w\" sizes=\"auto, (max-width: 628px) 100vw, 628px\" \/><\/figure>\n\n\n\n<p>This shows that at least in some important special cases, low rank $W$ produces low-dimension dynamics.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">The general case<\/h4>\n\n\n\n<p>More generally, using $\\|x_\\perp\\| \\le \\|x\\|$ and $\\|M\\| \\le 1$, we get $$ {\\mathcal{E}(x) \\over \\|x\\|} \\le \\| J_x \\| + \\sigma_{n+1} \\|J_y\\|.$$ We can reduce this bound by using a projection that has the same rank as our interactions matrix. This eliminates the second term, but the first term remains, and we&#8217;re no longer guaranteed to reduce reconstruction error to zero. Examples of this more general case are shown below:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"308\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-9-1024x308.png\" alt=\"\" class=\"wp-image-4963\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-9-1024x308.png 1024w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-9-300x90.png 300w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-9-768x231.png 768w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-9.png 1337w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption class=\"wp-element-caption\"><em>The data are for (a) epidemiological dynamics in a social network, (b) Wilson-Cowan dynamics on the C. elegans connectome, and Microbial population dynamics in a human gut microbiome.<\/em><\/figcaption><\/figure>\n\n\n\n<p>Despite the non-zero reconstruction error, the ansatz is still able to capture important dynamical properties, such as bifurcations, in each system:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"317\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-10-1024x317.png\" alt=\"\" class=\"wp-image-4964\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-10-1024x317.png 1024w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-10-300x93.png 300w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-10-768x238.png 768w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-10.png 1336w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Dimension reduction leads to emergence of higher-order interactions<\/h2>\n\n\n\n<p>The final point the authors make is that dimension reduction of dynamics on a network can produce higher-order interactions. This is shown schematically below:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"518\" height=\"880\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-11.png\" alt=\"\" class=\"wp-image-4967\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-11.png 518w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-11-177x300.png 177w\" sizes=\"auto, (max-width: 518px) 100vw, 518px\" \/><\/figure>\n\n\n\n<p>To see how this comes about, we start with our high dimensional network dynamics. The activity of each of the $N$ nodes is a function of its own activity, and a weighted combination of the rest of the nodes, $$ \\dot x_i = h_i(x_i, y_i), \\quad y_i = \\sum W_{ij} x_j.$$ If we assume that the $h_i$ are analytic functions, we can write it as<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"600\" height=\"137\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-12.png\" alt=\"\" class=\"wp-image-4971\" style=\"width:379px;height:auto\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-12.png 600w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-12-300x69.png 300w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/figure>\n\n\n\n<p>Under our ansatz $\\dot X = M f(M^\\dagger X),$ the reduced dynamics then become,<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"168\" src=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-13-1024x168.png\" alt=\"\" class=\"wp-image-4972\" srcset=\"https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-13-1024x168.png 1024w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-13-300x49.png 300w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-13-768x126.png 768w, https:\/\/sinatootoonian.com\/wp-content\/uploads\/2025\/10\/image-13.png 1229w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>and expanding the terms in brackets yields the higher-order interactions.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>In summary, the authors<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Provide empirical evidence that many real world networks, and some models of random matrices, have low effective rank.<\/li>\n\n\n\n<li>By using an ansatz for dimension-reduction of the high-dimensional vector field, show that low-effective rank of connectivity can, in some important cases, imply low-dimensional dynamics, capturable by projection onto a subspace determined by the connectivity.<\/li>\n\n\n\n<li>Show that such dimension reduction can generically produce high-order interactions among the observables.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>In this post I will summarize the paper &#8220;The low-rank hypothesis of complex systems&#8221; by Thibeault et al.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1,149],"tags":[135,136,127,49,134],"class_list":["post-4906","post","type-post","status-publish","format-standard","hentry","category-blog","category-journalclub","tag-complex-systes","tag-dimension-reduction","tag-journal-club","tag-low-rank","tag-tnjc"],"acf":[],"_links":{"self":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts\/4906","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/comments?post=4906"}],"version-history":[{"count":61,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts\/4906\/revisions"}],"predecessor-version":[{"id":5022,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts\/4906\/revisions\/5022"}],"wp:attachment":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/media?parent=4906"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/categories?post=4906"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/tags?post=4906"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}