Linearizing Non-linear Structures via Polynomial Lifting

This direction is split into other directions: Veronese mapping. Its last version stays readable and citable here.

Version 1 of 133 papers36 conceptsfrozen 2026-10-04

In machine learning and computer vision, we often encounter data that refuses to fit into a single linear model. Instead, it might lie on a curved surface (a hypersurface) or be scattered across a collection of different linear subspaces. While these structures are non-linear in their original space, a powerful recurring idea across algebraic geometry and optimization suggests that they are not inherently non-linear—they are simply "flat" objects viewed from the wrong perspective.

By "lifting" data into a higher-dimensional space of monomials—a process often called a Veronese mapping or polynomial embedding—we can transform complex algebraic varieties into simple linear subspaces. This transformation allows us to solve non-linear problems using the robust, well-understood tools of linear algebra.

The Intuition: Lifting to Linearize

Imagine a set of points in 2D that lie on a circle. There is no single line that can represent this data. However, if we map every point $(x, y)$ to a new 3D coordinate $(x^2, xy, y^2)$, the points that once formed a circle now lie on a flat plane in 3D.

This is the core mechanism behind Generalized Principal Component Analysis (GPCA), as detailed by Rene Vidal, Yi Ma, and Shankar Sastry in Generalized Principal Component Analysis (GPCA). By treating a union of multiple subspaces as the zero set of a single homogeneous polynomial, GPCA uses the Veronese map to "linearize" the segmentation problem. In the lifted space, identifying the underlying subspaces becomes a matter of finding the null space of a matrix using standard tools like Singular Value Decomposition (SVD).

From Subspaces to Hypersurfaces

The utility of this lifting extends beyond just grouping points. It provides a foundational way to rethink classification. In Foundational theory for optimal decision tree problems. II. Optimal hypersurface decision tree algorithm, Xi He demonstrates that the search for optimal non-linear decision boundaries—hypersurfaces—can be reframed as a linear optimization problem.

By mapping data into higher dimensions, curved boundaries are treated as linear hyperplanes. This allows the Optimal Hypersurface Decision Tree (HODT) algorithm to achieve significantly higher accuracy than traditional axis-parallel trees while maintaining the efficiency of linear solvers. Similarly, Xi He and Max A Little use this lifting in their Incremental Cell Enumeration (ICE) algorithm to find globally optimal solutions for 0-1 loss classification, challenging the assumption that non-linear optimization must be heuristic or iterative.

Measuring Complexity through Lifting

Lifting isn't just a computational trick; it is a lens for understanding the fundamental limits of learning. Researchers like Ilias Diakonikolas, Daniel Kane, and Lisheng Ren have used Veronese mappings to establish Statistical Query (SQ) lower bounds.

In SQ Lower Bounds for Learning Single Neurons with Massart Noise, they show that learning a single neuron is computationally hard by translating low-degree polynomials into linear functions in a higher-dimensional monomial space. This "representational strategy" allows them to take hardness results from simple linear models and project them onto more complex geometric structures, proving that certain non-linear learning tasks are fundamentally intractable.

Applications Across Domains

The "lifting" paradigm appears in various specialized fields, proving its versatility:

  • Computer Vision: Peter F. Sturm and João P. Barreto apply Veronese maps to General Imaging Geometry for Central Catadioptric Cameras. They turn the non-linear projections of curved mirrors into linear algebraic expressions, simplifying the geometry of complex camera systems.
  • Matrix Completion: In Tensor Methods for Nonlinear Matrix Completion, Greg Ongie, Rebecca Willett, and colleagues introduce Low Algebraic Dimension Matrix Completion (LADMC). They use Kronecker products to lift data into a tensor space, allowing them to recover missing values in matrices where the data lies on a non-linear variety rather than a single subspace.
  • Algebraic Statistics: Franz J. Király and others in Regression for sets of polynomial equations show that by multiplying equations by all possible monomials, one can embed a polynomial system into a higher-dimensional space to reveal its underlying linear "ideal" structure.

Why It Works: The Hilbert Function

The theoretical backbone of this approach often relies on Hilbert functions. As explored by Allen Y. Yang and Robert M. Fossum in Hilbert Functions and Applications to the Estimation of Subspace Arrangements, the Hilbert function provides a way to count the number of linearly independent polynomials that vanish on a set of points.

When we lift data into a higher-dimensional space, the "dimension" of the data in that new space tells us everything about its original non-linear structure—how many subspaces there are, what their dimensions are, and how they intersect. By moving to a space where polynomials behave like linear functions, we gain the ability to "see" the algebraic structure of the data through the simple lens of rank and nullity.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linearizing_non_linear_structures_via_po_0b5d54f7,
  title = {Linearizing Non-linear Structures via Polynomial Lifting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linearizing-non-linear-structures-via-polynomial-lifting/rdr_0b5d54f7fae949da85134355855af744},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_linearizing_non_linear_structures_via_po_0b5d54f7_v1,
  title = {Linearizing Non-linear Structures via Polynomial Lifting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linearizing-non-linear-structures-via-polynomial-lifting/rdr_0b5d54f7fae949da85134355855af744/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}