Fast Möbius transform An algebraic approach to information decomposition

The partial information decomposition (PID) and its extension integrated information decomposition (φID) are promising frameworks to investigate information phenomena involving multiple variables. An important limitation of these approaches is the high computational cost involved in their calculation. Here we leverage fundamental algebraic properties of these decompositions to enable a computationally-efficient method to estimate them, which we call the fast Möbius transform. Our approach is based on a formula for estimating the Möbius function that circumvents important computational bottlenecks and can in some cases offer a double-exponential speedup. We showcase the capabilities of this approach by presenting two analyses that would be unfeasible without this method: decomposing the information that neural activity at different frequency bands yields about the brain's macroscopic functional organization and identifying distinctive dynamical properties of the interactions between multiple voices in baroque music. Overall, our proposed approach illuminates the value of algebraic facets of information decomposition and opens the way to a wide range of future analyses.