🤖 machine learning

Sparse Orthogonal Regression Technique: A Spectral Framework for Equation Discovery, Approximation, and Integration

This paper introduces the Sparse Orthogonal Regression Technique (SORT), a spectral framework that utilizes L1-regularized regression to learn orthonormal-basis expansions directly from noisy data, offering a robust and flexible alternative to traditional library-based methods for discovering differential equations, approximating nonlinear functions, and estimating high-dimensional integrals.

Original authors: Sabin Roman, Ljupco Todorovski, Saso Dzeroski

Published 2026-08-14

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Sabin Roman, Ljupco Todorovski, Saso Dzeroski

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 a detective trying to solve a mystery, but the clues you find are messy, scattered, and sometimes missing. In the world of science and math, this is a common problem: we have data points—measurements of how things move, change, or interact—but we don't have the neat, perfect equations that describe them. Scientists have long tried to build "dictionaries" of possible mathematical shapes (like polynomials or waves) and hope that the true answer is hidden somewhere inside. If the right shape is in the dictionary, they can find it. But if the true answer is a weird shape that doesn't fit the dictionary, the whole investigation can crash.

To make sense of this messy data, scientists often use a technique called "sparse regression." Think of this as trying to describe a complex painting using only a few specific brushstrokes from a giant box of colors. You want to find the smallest set of strokes that still captures the whole picture, ignoring the noise and the extra paint that doesn't belong. The goal is to turn a chaotic cloud of numbers into a clean, understandable rule that can predict the future, calculate totals, or explain how a system works.

This is where a new method called SORT (Sparse Orthogonal Regression Technique) comes in. Instead of just hoping the right "brushstroke" is in a pre-made dictionary, SORT changes the game by building a custom, perfectly organized set of building blocks first. The researchers, Sabin Roman, Ljupčo Todorovski, and Sašo Džeroski, propose that if you arrange your data into a special, orderly grid (an "orthonormal basis") and then use a smart filter to pick out only the most important pieces, you can discover the rules of the universe even when the data is noisy or the sampling is sparse.

The Problem with Picking from a Menu

Imagine you are trying to guess the recipe for a secret soup. The old way (used by methods like SINDy) is to look at a menu of 100 standard ingredients—salt, pepper, carrots, onions—and try to find the combination that tastes right. If the soup actually uses a secret ingredient like "dragon fruit" that isn't on the menu, the chef (the computer) will struggle. It might try to force the flavor using a mix of carrots and onions, but the result will be wrong, or it might give up entirely if the data is a bit noisy.

The authors of this paper argue that this "menu approach" is too brittle. If the real world doesn't match the menu, the model breaks. They suggest a different strategy: instead of guessing from a fixed list, build a flexible, mathematical scaffold that can hold any shape, and then let the data tell you which parts of that scaffold are actually being used.

How SORT Works: The Musical Analogy

Think of SORT like tuning a piano to play a song you've never heard before.

The Scaffold (The Basis): Instead of guessing which notes are in the song, SORT starts with a full set of perfectly tuned, independent notes (an orthonormal basis). These notes don't interfere with each other; if you play one, it doesn't accidentally make another sound louder or quieter. This is the "orthogonal" part.
The Filter (Sparsity): The song you are trying to find is likely simple, even if the recording is full of static. SORT uses a mathematical filter (L1-regularized regression) to listen to the noisy recording and ask: "Which of these notes are actually playing, and which ones are just static?" It turns down the volume on the noise and keeps only the few notes that matter.
The Result: You end up with a list of coefficients (numbers) that tell you exactly how loud each note should be. This list is your "sparse" representation of the song.

What They Found: Robustness and Flexibility

The researchers tested SORT on several challenging scenarios, and the results were quite revealing.

1. When Data is Messy and Sparse
In one experiment, they tried to figure out the rules of famous animal population cycles (like predators and prey) and swinging pendulums. They gave the computer data that was sampled very far apart in time, making it hard to tell how fast things were changing.

The Old Way: The traditional "menu" method (SINDy) often failed spectacularly. When the data was too coarse, the model would suddenly go haywire, predicting that a population would explode to infinity or vanish instantly.
The SORT Way: SORT was much more stable. Even when the data was rough, it didn't crash. It degraded gracefully, meaning the predictions got a little worse but stayed within the realm of possibility. It was like a car with better suspension; it could handle the bumpy road without flipping over.

2. When the Recipe is Unknown
They also tested a system where the "secret ingredient" was a Bessel function (a complex mathematical wave shape) that isn't found in standard polynomial menus.

The Old Way: The menu-based method struggled because the true shape wasn't in its dictionary. It tried to force a square peg into a round hole, and the error grew as the data got noisier.
The SORT Way: Because SORT doesn't rely on a fixed list of ingredients, it could approximate the Bessel function using its flexible scaffold. It remained robust even when the "true" shape was something the old method didn't expect.

3. Doing Math Without the Math
One of the coolest tricks SORT can do is calculate integrals (which are like finding the total area under a curve or the total amount of something over time). Usually, you need complex formulas to do this. But with SORT, once you have your list of coefficients, you can just "read off" the answer.

The Analogy: Imagine you want to know the total weight of a pile of sand. Instead of weighing every grain, you build a model of the pile using a few key measurements. SORT lets you look at the "coefficient" for the total volume and instantly know the answer. They tested this on oscillating waves and smooth curves, and it worked surprisingly well, even in high dimensions.

4. Growing the Model Without Breaking It
Finally, they looked at what happens when you make the model more complex. In many machine learning systems, adding more complexity changes everything—the old answers become wrong because the whole structure shifts.

The SORT Way: Because SORT uses a stable, ordered scaffold, adding more "notes" to the song doesn't change the meaning of the notes you already found. If you add a high-frequency note, the low-frequency notes stay exactly the same. This allows scientists to grow their models step-by-step, checking at each step if the new complexity actually helps, without losing the ground they've already covered.

The Takeaway

The paper doesn't claim to have solved every mystery in the universe. It suggests that for many problems, especially where data is noisy or the underlying rules are unknown, relying on a fixed dictionary of mathematical terms is risky.

Instead, SORT proposes a middle ground: use a flexible, mathematically perfect scaffold to hold the data, and then use sparsity to find the simple, clean pattern hiding inside. It's not about finding the "perfect" symbolic equation immediately; it's about finding a stable, reusable representation first. This representation can then be used to predict the future, calculate totals, or even guide scientists toward the simpler, human-readable formulas they might be looking for later.

In short, SORT is a new way to listen to the noisy music of the universe, tune out the static, and find the melody without needing to know the song in advance. It suggests that by designing our mathematical tools to be adaptable and ordered, we can make our discoveries more robust and our models more reliable.

Technical Summary: Sparse Orthogonal Regression Technique (SORT)

Problem Statement
Scientific computing and machine learning frequently require learning an unknown functional relationship from finite, noisy, and often irregularly sampled data. This challenge spans three primary domains: surrogate modeling for expensive simulations, numerical integration from sampled observations, and the data-driven discovery of governing ordinary differential equations (ODEs). Existing approaches often treat these tasks separately. Furthermore, popular equation discovery methods, such as SINDy (Sparse Identification of Nonlinear Dynamics), rely on regressing derivatives onto finite libraries of candidate nonlinearities. While effective when the correct terms exist in the library, these methods can become ill-conditioned or brittle if the true dynamics are not sparse in the chosen dictionary or if derivative estimates are degraded by coarse sampling or noise.

Methodology
The paper introduces the Sparse Orthogonal Regression Technique (SORT), a spectral framework that learns orthonormal-basis expansions directly from observations without requiring explicit quadrature or analytic inner-product evaluation.

Core Mechanism: SORT represents functions (such as vector fields in dynamical systems or integrands) as expansions in a prescribed orthonormal basis $\{ \phi_k \}$ . Instead of computing coefficients via projection integrals, SORT estimates the expansion coefficients $\hat{c}$ by solving an $L_1$ -regularized regression problem (LASSO) on the observed data points:
$\hat{c} \in \arg \min_{u} \frac{1}{2N} \| y - \Phi u \|_2^2 + \lambda \| u \|_1$
where $\Phi_{ik} = \phi_k(x_i)$ is the design matrix constructed from the basis functions evaluated at sample points.
Basis Design: The framework emphasizes that basis selection is a scientific modeling decision, not merely an implementation detail. Depending on the domain, users may select Fourier bases for periodic structures, Legendre/Chebyshev for bounded intervals, or Hermite/Laguerre for unbounded domains.
Workflow: The method does not claim algorithmic novelty in sparse regression on orthogonal features but rather proposes a unified workflow where the learned sparse spectral representation serves as a reusable intermediate object for downstream tasks.

Key Contributions and Applications

Equation Discovery (Dynamical System Reconstruction):
- SORT represents vector field components as sparse spectral expansions. This offers a complementary route to symbolic regression and library-based sparse identification.
- Robustness: Experiments show that while SORT matches SINDy performance under fine sampling, it degrades more gracefully under coarse sampling and noisy derivative estimates.
- Representation Mismatch: In systems where the true nonlinearity (e.g., Bessel functions) is not sparse in standard polynomial or trigonometric libraries, SINDy-style methods fail or become brittle. SORT remains robust because it approximates the vector field in a fixed orthonormal coordinate system where sparsity suppresses unstable modes, shifting the burden from "selecting the correct library term" to "designing an appropriate basis."
Numerical Integration via Coefficient Readout:
- SORT treats numerical integration as a linear functional problem. If a basis element is chosen to represent the integration functional (the Riesz representer), the integral of the function is proportional to the corresponding coefficient.
- The method estimates this coefficient directly from scattered point samples via sparse regression, bypassing the need for explicit quadrature rules. This is particularly useful for high-dimensional or irregularly sampled data where traditional quadrature is difficult.
Order-Consistent Model Growth:
- A distinct feature of orthonormal expansions is that increasing the truncation order refines the approximation without altering the meaning of lower-order coefficients.
- SORT leverages this to provide a diagnostic for stable learning: dominant low-order coefficients persist as model complexity increases. This contrasts with many machine learning workflows where increasing model size changes the entire parameterization, making model comparison difficult.

Experimental Results
The authors evaluate SORT against dense least-squares, kernel-based methods, and library-based sparse regression (SINDy) across several benchmarks:

Sampling Degradation: On systems like Lotka-Volterra and Van der Pol, SINDy exhibits abrupt failure as sampling intervals increase, whereas SORT maintains bounded, gradual degradation.
Noise and Mismatch: In cyclic systems (Thomas attractor and a Bessel-driven variant), SORT performs comparably to SINDy when the basis matches the dynamics. However, in the Bessel-driven system (where the nonlinearity is not sparse in standard libraries), SORT remains robust while SINDy degrades significantly under noise and reduced training data.
Integration: SORT accurately estimates 1D and high-dimensional separable integrals (Gaussian and Fresnel-type) across varying parameters, matching closed-form solutions where available.
Approximation: In approximating functions like $f(x)=x$ and $f(x_1, x_2) = \exp(x_1 \cos(2x_2))$ , SORT recovers stable low-order spectral structures and achieves lower test error than dense monomial or random feature baselines, preserving a stable hierarchy of coefficients as model size grows.

Significance and Claims
The paper positions SORT not as a new optimization algorithm, but as a task-oriented recombination of established tools (orthonormal bases and sparse regression) designed to create a stable, reusable intermediate representation.

Scientific Modeling: The authors argue that basis design is an explicit part of the scientific modeling problem. SORT facilitates this by allowing researchers to adapt the basis to the problem domain (e.g., using Bessel functions for radial symmetry) rather than relying on generic, brittle library selection.
Intermediate Representation: SORT provides a bridge between raw, noisy samples and final analytic descriptions. It allows for the recovery of a stable spectral representation first, which can subsequently guide searches for simpler symbolic forms if desired.
Stability: The primary claim is that sparse orthogonal expansions offer a more stable route to equation discovery, integration, and approximation under conditions of noise, sparse sampling, and representation mismatch, particularly when the "correct" analytic building blocks are unknown or poorly matched by standard libraries.

The Problem with Picking from a Menu

How SORT Works: The Musical Analogy

What They Found: Robustness and Flexibility

The Takeaway

More like this