🔢 mathematics

Concise $(\varepsilon,r)$ -representations of a path

This paper investigates the optimal trade-off between time discretization (intervals $m$ ) and signature degree ( $N$ ) for concisely representing paths to approximate solutions of linear controlled differential equations within a specified accuracy $\varepsilon$ , demonstrating that the most memory-efficient representation typically lies between the extremes of pure time-series and pure signature approaches.

Original authors: Emilio Ferrucci, Oliver Perrée, Terry Lyons

Published 2026-07-30

📖 9 min read🧠 Deep dive

CC BY 4.0

Original authors: Emilio Ferrucci, Oliver Perrée, Terry Lyons

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message to a friend, but the message is a long, winding journey taken by a tiny robot. The robot's path is the data. In the world of mathematics and computer science, specifically a field called "rough path theory," scientists have long known that simply listing the robot's coordinates every second (a time series) isn't always enough. If the robot zips around wildly, that list misses the "shape" of the journey. Instead, mathematicians use a special tool called a "signature," which is like a recipe of all the twists, turns, and loops the robot made. This recipe is built from "iterated integrals," a fancy way of measuring how the path interacts with itself over time.

The big question is: How do you write down this recipe so it takes up the least amount of space in your computer's memory, but still lets you predict exactly where the robot will end up if you push it with a certain force? Think of it like packing a suitcase. You could take a photo of every single step the robot took (a lot of data, very precise), or you could just write down the start and end points (very little data, but you lose all the details). The paper asks: Is there a "Goldilocks" packing method that isn't too big and isn't too small, but just right?

This paper, written by Emilio Ferrucci, Oliver Perrée, and Terry Lyons, tackles that exact packing problem. They look at two main ways to compress the robot's journey: breaking the trip into many small segments and describing each with a simple summary, or keeping the trip as one big chunk but describing it with a very complex, high-level summary. The authors prove that the best solution is almost never one of these two extremes. Instead, the most efficient way to store the data is to find a sweet spot in the middle: use a moderate number of segments and a moderate level of complexity for the summary.

The researchers found that if you need to predict the robot's path with high precision (a tiny margin of error) or if the forces pushing the robot are very strong, you should actually use a much more complex summary than you might guess. They showed that as you demand higher accuracy, the optimal strategy is to increase both the number of segments and the depth of the summary simultaneously. They demonstrated this using mathematical proofs for smooth paths and computer simulations for random, jittery paths (like those found in stock markets or electricity usage data). Their results suggest that for many real-world problems, sticking to the simplest summaries is a mistake; a slightly more complex, "in-between" approach saves memory while keeping the predictions accurate.

The Robot's Journey and the Memory Puzzle

Let's dive into the story of the robot. Imagine you are a data scientist trying to store the history of a robot's movement. The robot moves through a space with $d$ dimensions (like a 3D room, so $d=3$ ). Its path is a continuous line from time $0$ to time $T$ .

The Old Way: The Time Series
Traditionally, we store this path as a list of coordinates: "At time 1, it was at (1, 2); at time 2, it was at (1.1, 2.1)." This is like taking a photo every second. If the robot moves smoothly, this works fine. But if the robot is jittery, dancing, or vibrating wildly, you need thousands of photos just to capture the wiggles. This takes up a huge amount of memory.

The New Way: The Signature
Mathematicians discovered a better way. Instead of photos, they use a "signature." Think of the signature as a set of ingredients that describe the shape of the path.

Level 1: How far did it go? (The straight-line distance).
Level 2: Did it turn left or right? (The area it swept out).
Level 3: Did it twist into a spiral? (The volume it swept out).
And so on...

This collection of ingredients is called the iterated integrals. It captures the geometry of the path perfectly, even if the path is very rough. However, listing all these ingredients (up to infinity) takes infinite memory. So, we have to cut it off at some point, say, Level $N$ . This is called a truncated signature.

The Compression Dilemma
Now, we have a problem. We want to store the path using the least memory possible, but we also need to be able to solve a specific type of math problem: a Linear Controlled Differential Equation (CDE).
Imagine the robot is being pushed by a force (represented by a matrix $A$ ). We want to know where the robot ends up after being pushed. The equation is $dY = AY dX$.

The Constraint: We must be able to solve this equation for any push strength up to a limit $r$ , with an error no bigger than $\epsilon$ (a tiny number).
The Goal: Minimize the memory used.

We have two knobs to turn to compress the data:

$m$ (The Number of Intervals): We can chop the path into $m$ smaller pieces. If $m$ is huge, we have many small pieces.
$N$ (The Degree of the Signature): For each piece, we can describe it with a signature up to level $N$ . If $N$ is huge, we have a very detailed description of each piece.

The Naive Guesses
Most people would guess one of two "naive" strategies:

Strategy A ( $N=1$ ): Chop the path into millions of tiny pieces ( $m$ is huge), but only describe each piece with a simple straight line ( $N=1$ ). This is like taking a million photos but only writing down "I moved 1 inch."
Strategy B ( $m=1$ ): Keep the path as one big chunk ( $m=1$ ), but describe it with a super-detailed, complex signature ( $N$ is huge). This is like taking one photo but trying to describe every single pixel in the universe.

What the Paper Actually Found
The authors, Ferrucci, Perrée, and Lyons, asked: "Is one of these naive strategies the best?"

They proved the answer is no. The optimal strategy lies strictly in between these two extremes.

Here is the breakdown of their findings:

The Sweet Spot: The best way to store the data is to use a moderate number of intervals ( $m$ ) and a moderate level of detail ( $N$ ). You don't need millions of tiny pieces, and you don't need a single, impossibly complex description. You need a balance.
The Effect of Precision ( $\epsilon$ ) and Force ( $r$ ):
- If you need higher accuracy (smaller $\epsilon$ ), you should increase both $N$ and $m$ .
- If the force is stronger (larger $r$ ), you should also increase both $N$ and $m$ .
- Crucially, they found that as you demand more precision, the optimal $N$ grows. This is surprising because higher $N$ usually means much more memory (the "curse of dimensionality"). But for these specific equations, storing a higher-level signature is actually more efficient than chopping the path into more pieces.
The Math Behind the Magic:
- They derived a formula for the optimal $N^*$ (the best level of detail). It grows roughly like the square root of the logarithm of the required precision.
- They showed that the memory cost of this "in-between" strategy is significantly lower than the cost of the naive strategies. In their simulations, the naive strategies were "suboptimal," meaning they wasted memory.
Rough Paths and Randomness:
- The paper also looked at paths that are not smooth, like Brownian motion (the random jitter of a pollen grain in water) or fractional Brownian motion.
- Even for these random paths, the same rule applies. The best strategy is to use a higher $N$ than you might think necessary. For example, if a path is "rough" enough to require a level 2 signature to be defined, the optimal storage might actually require a level 6 or 7 signature to be memory-efficient.
- They tested this with computer simulations using fractional Brownian motion (a type of random path) and confirmed that picking a higher $N$ dramatically reduced the storage cost while keeping the error low.

Why This Matters
This isn't just about saving space on a hard drive. It changes how we think about data.

Machine Learning: In AI, we often use signatures to feed data into neural networks. This paper suggests that we shouldn't just use simple signatures or chop data into tiny pieces. We should find the "Goldilocks" zone to get the best performance with the least computing power.
Real-World Data: The authors showed an example using electricity data from homes (voltage and current). They found that for these real-world signals, the "in-between" strategy provided a much more compact summary than the raw data or the simple summaries.

What They Didn't Do
It's important to note what this paper didn't do:

They didn't claim this works for every possible equation. They focused specifically on linear equations (where the force is proportional to the position). They noted that for non-linear equations, the math is much harder and the "factorial decay" (the magic that makes high $N$ efficient) might not happen in the same way.
They didn't solve the problem for all types of random noise, but they did show it works for Brownian motion and fractional Brownian motion.
They didn't say "Strategy A is bad." They said "Strategy A is not the best." In some specific, weird cases, a naive strategy might be okay, but the "in-between" strategy is generally superior.

The Takeaway
If you are trying to compress a complex path to solve a math problem, don't go to the extremes. Don't just take a million photos, and don't just write one giant paragraph. Find the middle ground. Use a moderate number of segments and a moderately complex description. The paper proves that this "in-between" approach is the mathematical champion for saving memory while keeping your predictions accurate. It's a reminder that in the world of data, the middle path is often the most efficient one.

Technical Summary: Concise $(\varepsilon, r)$ -representations of a path

Problem Statement
The paper addresses the problem of optimally representing continuous sequential data (paths $X: [0, T] \to \mathbb{R}^d$ ) in finite memory. Traditional representations as time series are often insufficient for oscillatory signals or for defining solutions to controlled differential equations (CDEs). While the signature (a collection of iterated integrals) provides a rich, universal representation, storing the full signature is computationally expensive.

The authors formalize a trade-off between two naive encoding strategies:

High resolution, low degree: Storing a time series with many intervals ( $m$ large) but low-order features ( $N=1$ ).
Low resolution, high degree: Storing a single interval with high-order iterated integrals ( $m=1$ , $N$ large).

The goal is to find the optimal pair $(N, m)$ that minimizes the storage cost (measured by the number of real values required to store the truncated log-signature) subject to the constraint that the representation must approximate solutions to linear CDEs $dY = AY dX$ with a tensor norm $|A| \le r$ to an accuracy of at least $\varepsilon$ . This is framed as finding an $(\varepsilon, r)$ -concise representation.

Methodology
The authors analyze this optimization problem across three distinct regimes of path regularity:

Bounded Variation ( $p=1$ ):
- The error of the degree- $N$ Euler scheme is bounded in terms of the 1-variation norm $\|X\|_{1\text{-var}}$ .
- The storage cost is modeled as $m \Lambda_d(N)$ , where $\Lambda_d(N)$ is the dimension of the free Lie algebra truncated at degree $N$ .
- The authors derive the asymptotic behavior of $\Lambda_d(N)$ and establish a sharp error bound for the Euler scheme that decays factorially in $N$ and polynomially in $m$ .
- They formulate a constrained optimization problem, relaxing $N$ and $m$ to continuous variables, and solve for the unique minimizer using asymptotic analysis as $r \to \infty$ and $\varepsilon \to 0^+$ .
Bounded $p$ -Variation ( $p > 1$ ):
- For rough paths, the authors derive a new error estimate for the degree- $N$ Euler scheme applied to linear CDEs. Crucially, they prove that the error decays factorially in $N$ (a property specific to linear equations) and polynomially in $m$ , even when $m$ is fixed.
- They note that formulating the optimization problem analytically is difficult because the error bound depends on the $p$ -variation curve of the path (an infinite-dimensional quantity) and the parameter $p$ itself.
- Instead of a purely analytical solution, they advocate for an empirical approach: solving batches of RDEs to measure errors and determine optimal $(N, m)$ pairs. They demonstrate this using "toy" smooth paths that approximate pure level- $\nu$ rough paths.
Stochastic Processes ( $L^2$ setting):
- The problem is extended to paths sampled from stochastic processes (e.g., Brownian motion with drift), where error is measured in $L^2$ .
- Using martingale arguments and properties of the signature of Brownian motion, the authors derive an $L^2$ -Euler error estimate.
- Similar to the deterministic cases, they show that the error exhibits factorial decay in $N$ and polynomial decay in $m$ .
- They apply this to fractional Brownian motion (fBm) with Hurst parameter $H > 1/4$ , validating the approach empirically.

Key Contributions and Results

Optimal Trade-off: The paper proves that the optimal representation generally lies strictly between the two naive extremes ( $N=1$ or $m=1$ ).
- Asymptotics: As the norm bound $r$ increases or the tolerance $\varepsilon$ decreases, both the optimal truncation degree $N^*$ and the optimal number of intervals $m^*$ diverge to infinity.
- Scaling Laws: The authors derive specific asymptotic rates. For the bounded variation case, $N^* \sim \sqrt{\frac{\log(r e^r / \varepsilon)}{\log d}}$ and $m^*$ grows sub-polynomially in $1/\varepsilon$ but stretched-exponentially in $r$ .
- Storage Efficiency: The optimal storage footprint grows significantly slower than the naive choices. Specifically, Proposition 1.6 shows that the optimal cost is asymptotically negligible compared to the cost of the naive strategy $(1, m^\circ)$ .
Factorial Decay in Linear CDEs: A central theoretical result is the derivation of an error bound for the Euler scheme on linear CDEs that decays factorially in $N$ . This is highlighted as a special feature of linear equations, distinguishing them from non-linear RDEs where such decay is not guaranteed for fixed $m$ .
Rough Path Theory for Smooth Paths: The authors demonstrate that rough path theory is valuable even for smooth paths. By allowing $N > 1$ , one can estimate errors using norms (like $p$ -variation for $p > 1$ ) that are more favorable than the 1-variation norm, particularly when the path has large 1-variation but is geometrically simple.
Stochastic Extension: The paper provides an $L^2$ error estimate for linear SDEs with drift, showing similar factorial decay properties. Empirical studies on fractional Brownian motion confirm that choosing $N$ significantly higher than the intrinsic roughness $\lfloor H^{-1} \rfloor$ (and even higher than 1) often yields better storage efficiency.

Significance and Claims
The paper claims to reveal deep insights into the nature of approximate sequential data. It posits that the "intrinsic roughness" and dimensionality of a path are not absolute properties but are defined relative to a reference choice of accuracy $\varepsilon$ and complexity bound $r$ .

The authors emphasize that while the log-signature suffers from the "curse of dimensionality" (the dimension $\Lambda_d(N)$ grows exponentially), it is still beneficial to store signatures at higher degrees for equations with high norms or when high precision is required. This contradicts the intuition that one should always minimize $N$ to save space.

The work bridges the gap between the machine learning literature (which often focuses on high-degree signatures for universality) and numerical analysis (which often focuses on refining partitions). By quantifying the trade-off, the paper provides a theoretical basis for "lossy compression" of path data that is tailored to the specific requirements of solving linear differential equations. The authors conclude that for many practical datasets (such as the electrical load data shown in Figure 1), truncated log-signatures over appropriately sized intervals offer a much more compact and informative summary than raw time series.

The Robot's Journey and the Memory Puzzle

More like this