When fitting complex models to data, we often face optimization landscapes riddled with local minima, poor conditioning, and slow convergence. However, many of the most challenging nonlinear optimization problems possess a hidden structural saving grace: separability.
A problem is separable if its variables can be partitioned into two sets: one that enters the objective function linearly, and another that enters nonlinearly. Instead of optimizing all variables simultaneously—a strategy that forces linear and nonlinear parameters to "fight" each other during gradient descent—we can use a technique called Variable Projection (VarPro). By mathematically eliminating the linear parameters from the optimization objective, VarPro reduces the dimensionality of the problem and drastically smooths the optimization landscape.
The Intuition: Why Joint Optimization Fails
To understand why Variable Projection works, consider a simple data-fitting problem. Imagine trying to fit a signal to a sum of decaying exponentials:
$$y \approx c_1 e^{-\alpha_1 t} + c_2 e^{-\alpha_2 t}$$
Here, the coefficients ($c_1, c_2$) are linear parameters, while the decay rates ($\alpha_1, \alpha_2$) are nonlinear parameters.
If we attempt to solve this using standard joint optimization (such as standard gradient descent or the Levenberg-Marquardt algorithm), the solver treats $c$ and $\alpha$ as a single, combined set of coordinates. As noted by Zach et al., failing to exploit this separable structure leads to slower convergence and a high likelihood of getting trapped in poor local optima.
Why does this happen? If the optimizer takes a step that slightly worsens the nonlinear parameters $\alpha$, the current linear parameters $c$ instantly become highly suboptimal. The two sets of parameters become tightly coupled, creating narrow, twisting valleys in the optimization landscape where solvers easily stall.
The Mechanism: Projecting Out the Linear Weights
Variable Projection breaks this coupling by recognizing a fundamental asymmetry: if we happen to know the exact values of the nonlinear parameters, finding the optimal linear parameters is trivial. It is simply a linear least-squares problem that can be solved analytically in a single step using the Moore-Penrose pseudoinverse.
Mathematically, we can express the optimal linear parameters as a direct function of the nonlinear parameters:
$$c^*(\alpha) = \Phi(\alpha)^\dagger y$$
where $\Phi(\alpha)$ is the matrix of nonlinear basis functions and $\dagger$ denotes the pseudoinverse.
The core breakthrough of VarPro is to substitute this analytical solution directly back into the original objective function. This "projects out" the linear variables, leaving a reduced objective function that depends only on the nonlinear parameters $\alpha$.
This algebraic elimination changes the game in two profound ways:
- Dimensionality Reduction: The search space shrinks because the optimizer only needs to navigate the coordinates of the nonlinear parameters.
- Guaranteed Conditional Optimality: At every single iteration of the outer optimization loop, the linear parameters are guaranteed to be perfectly optimal relative to the current nonlinear parameters.
As Strelow explains, this variable elimination creates a significantly smoother optimization landscape. Because the linear parameters are never "out of sync" with the nonlinear ones, the solver avoids the chaotic local minima that plague joint optimization, resulting in highly reliable convergence even from poor initializations.
Joint Optimization: (Nonlinear α, Linear c) ---> Simultaneous Iterative Updates
Variable Projection: (Nonlinear α) ---> Analytical Linear Solver ---> Optimal c*(α)
Application Across Domains
Because separable structures appear everywhere in science and engineering, Variable Projection has been independently discovered and adapted across a wide array of disciplines.
Deep Learning and Reinforcement Learning
Most deep neural networks end with a linear classification or regression layer. Newman et al. leverage this by applying VarPro to network training. By mathematically eliminating the final layer's linear weights, they ensure the network's output layer is always optimal relative to the hidden features. This improves the conditioning of the optimization problem, leading to faster convergence and better generalization than standard joint optimizers like Adam.
Similarly, in reinforcement learning, feature engineering often relies on choosing the right basis functions (like radial basis functions). Mahadevan et al. use VarPro to separate the optimization of linear value-function weights from the nonlinear parameters governing the basis functions themselves, simplifying feature adaptation.
Computer Vision and 3D Reconstruction
In Bundle Adjustment—the process of refining 3D structures and camera poses from images—joint optimization frequently fails without a near-perfect initial guess. Zach et al. demonstrate that by algebraically eliminating 3D point coordinates, the optimization can focus solely on camera poses. This formulation avoids the local minima that typically ruin bilinear reconstructions, enabling initialization-free bundle adjustment.
This strategy extends to other imaging modalities: van Leeuwen et al. embed image reconstruction within the search for alignment parameters in 3D tomography, while Feng et al. project out wavefield variables to isolate medium parameters in ground-penetrating radar inversions.
Signal Processing and Data Fitting
In time-series analysis, Dynamic Mode Decomposition (DMD) fits data to exponential sums. Askham applies VarPro to eliminate mode amplitudes, focusing the optimization entirely on system eigenvalues. This stabilizes the fit and eliminates the eigenvalue bias caused by noise.
The same principle allows Tsaig et al. to optimize decimation filters in image compression by eliminating interpolation parameters, and enables Yu to efficiently fit complex, multi-phase power-law functions to massive datasets of YouTube video lifecycles.
Advanced Refinements
While the classic VarPro framework is powerful, recent research addresses its behavior under non-ideal conditions.
When fitting models where the data contains significant noise or model mismatch, the "residual" (the error at the optimal solution) remains large. Chen et al. analyzed how parameter coupling affects the Jacobian matrix in these scenarios, introducing adaptive refinements to handle large-residual problems smoothly.
Additionally, while VarPro traditionally relies on batch matrix operations, Su et al. developed an online version that eliminates linear parameters in real-time using a window of past errors, making VarPro viable for streaming data and dynamic systems. Finally, the core philosophy of VarPro has even been extended to non-smooth optimization: Poon et al. show that minimizing over auxiliary variables in a bi-level fashion can smooth out non-differentiable objectives, allowing standard gradient-based solvers to handle complex structural priors efficiently.
Key Foundational Work
General and Nested Wiberg Minimization: L 2 and Maximum Likelihood (2012) — contributed 2 concept elements to this direction.
Variable projection for near-optimal filtering in low bit-rate block coders (2005) — contributed 2 concept elements to this direction.