Linearizing Non-Linear Structures with Veronese Mapping

22 concepts20 papers1 proposal

Imagine trying to separate a cluster of red points inside a circle from blue points outside it. In two dimensions, a straight line cannot separate them; you need a curved, quadratic boundary ($x^2 + y^2 = r^2$). However, if you map every point $(x, y)$ to a three-dimensional space where the coordinates are $(x^2, y^2, \sqrt{2}xy)$, that circular boundary becomes a perfectly flat plane.

This is the core intuition behind coordinate lifting and the Veronese mapping: by embedding low-dimensional data into a higher-dimensional space composed of its monomials, non-linear curves, surfaces, and decision boundaries become flat, linear hyperplanes. Once linearized, the entire toolkit of linear algebra, linear programming, and hyperplane geometry can be brought to bear on problems that initially appeared mathematically intractable.

The Mathematical Engine

Formally, a Veronese map (or monomial expansion) of degree $d$ takes a vector of variables and maps it to a vector containing all possible monomials of degree $d$. For a simple 2D coordinate $(x, y)$, a second-order Veronese mapping yields a higher-dimensional vector:

$$\phi(x, y) = [x^2, y^2, xy, x, y, 1]^T$$

To see why this linearizes non-linear equations, consider a general quadratic curve:

$$A x^2 + B y^2 + C xy + D x + E y + F = 0$$

In the original 2D space, this defines a conic section (an ellipse, parabola, or hyperbola). But if we rewrite this expression as a dot product between a coefficient vector $\mathbf{w} = [A, B, C, D, E, F]^T$ and our lifted vector $\phi(x, y)$, it simplifies to a standard linear equation:

$$\mathbf{w} \cdot \phi(x, y) = 0$$

The non-linear geometry has been completely absorbed into the coordinate representation, leaving the relationship between the parameters and the lifted coordinates perfectly linear.

Straightening the Lens: Computer Vision

Traditional computer vision relies heavily on linear projective geometry. For instance, matching points between two standard cameras involves a fundamental matrix that defines linear epipolar lines. But when cameras use wide-angle fish-eye lenses, parabolic mirrors, or suffer from severe radial distortion, these straight lines warp into complex curves, breaking standard algorithms.

Instead of dealing with messy non-linear optimization, researchers use coordinate lifting to restore linearity. Bill Triggs demonstrated that mapping image coordinates into higher-dimensional tensor products allows non-linear projective constraints across multiple views to be represented as simple linear relationships.

For specialized hardware like parabolic catadioptric (mirror-based) cameras, Geyer et al. showed that lifting 2D image points into a 4D projective space allows a $4 \times 4$ "catadioptric fundamental matrix" to capture complex mirror geometry linearly. Expanding on this, Sturm et al. utilized a fourth-order monomial expansion to map coordinates into a 14-dimensional projective space, successfully linearizing the epipolar geometry for all central catadioptric systems.

Original Space (2D)             Veronese Lifting             Lifted Space (Higher-D)
  [ Curved Epipolar Lines ]   ====================>   [ Flat Hyperplanes / Linear Matrices ]
  (Non-linear projections)                             (Standard Matrix Operations)

This trick works even when the distortion parameters are completely unknown. José Henrique Brito extended the standard fundamental matrix by lifting image coordinates to jointly estimate epipolar geometry and lens distortion parameters directly from raw point correspondences, bypassing the need for explicit calibration patterns.

Mapping the Boundaries of Learning Theory

The power of the Veronese map extends far beyond physical cameras into computational learning theory. When analyzing the difficulty of training neural networks or classifiers, researchers often face non-linear decision boundaries. By lifting the input space, they can translate these complex boundaries into standard linear halfspaces to prove complexity bounds or design exact algorithms.

Quantifying Expressive Capacity

Roman Vershynin settled a long-standing question about the storage capacity of polynomial threshold functions (neurons with polynomial activation). By treating each unique monomial as a separate coordinate, the author mapped non-linear decision surfaces into linear hyperplane arrangements, proving that a degree-$d$ polynomial neuron can store approximately $n$ bits per monomial term.

Proving Computational Hardness

Lifting is a vital reduction technique for establishing when a problem is computationally intractable. For instance, Kane et al. used high-dimensional monomial expansions to show that learning a polynomial over original features is equivalent to learning a single neuron in the expanded space. This representational shift allowed them to prove that adversarial label noise makes even a single ReLU or Sigmoid neuron hard to optimize.

Similarly, Diakonikolas et al. applied polynomial lifting to project input data into higher dimensions, extending cryptographic hardness results from simple linear halfspaces to complex geometric structures. This strategy has been widely adopted to establish Statistical Query (SQ) lower bounds:

  • Diakonikolas et al. used a Veronese mapping to translate low-degree polynomials into linear functions, proving the intractability of learning single neurons under Massart noise.
  • Stefan Tiegel leveraged Veronese mappings to convert polynomial threshold functions back into standard halfspaces, establishing tight lower bounds for learning intersections of halfspaces.
  • Diakonikolas et al. demonstrated the super-polynomial hardness of multiclass linear classification with random noise by using higher-order feature mappings to convert polynomial decision boundaries into a linear task.

Designing Global Optimizers

Conversely, lifting can make non-linear optimization provably solvable. He et al. developed an algorithm for the notoriously difficult 0-1 loss classification problem. By lifting input features via a Veronese mapping, they enabled combinatorial linear optimization techniques to find globally optimal, non-linear decision boundaries (like quadratic curves) in polynomial time.

Subspaces, Graphs, and Optimization

Beyond vision and learning, coordinate linearization simplifies structural problems across applied mathematics.

Subspace Clustering

When data points lie on a union of multiple moving hyperplanes or subspaces, the global structure can be modeled as a single high-degree polynomial whose zeros represent the data. Yang et al. leveraged Veronese embeddings to transform the problem of identifying a union of subspaces into a linear problem in polynomial space, using algebraic Hilbert functions to segment the data. For dynamic scenes, Rene Vidal employed a Veronese map to track moving hyperplanes in real-time, converting a non-linear optimization landscape into a sequence of linear estimations.

Rigidity and Algebraic Integration

In discrete geometry, testing whether a framework can flex or remains rigid independent of its embedding dimension is highly non-linear. Connelly et al. used the Veronese map to transform geometric separation problems involving quadric surfaces into linear algebraic problems, yielding an efficient linear programming approach to test for the universal rigidity of bipartite graphs.

Even pure algebraic integration benefits from this perspective. Lasserre et al. showed that mapping homogeneous polynomials into a higher-dimensional space allows them to behave as linear functions, which dramatically simplifies the integration of complex forms over sublevel sets by exploiting the flat geometric properties of the Veronese variety. Finally, in algorithmic computer science, Josh Alman solved the "Light Bulb Problem" (finding correlated vectors) by expanding vector interaction polynomials into monomials, turning a complex polynomial evaluation task into a standard, highly optimized matrix inner product.

Key Foundational Work

Structure and Motion from Uncalibrated Catadioptric Views (2001) — contributed 4 concept elements to this direction.
Mirrors in motion: Epipolar geometry and motion estimation (2003) — contributed 1 concept elements to this direction.
Joint Feature Distributions for Image Correspondence (2001) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_veronese_mapping_98d06ceb,
  title = {Veronese mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/veronese-mapping/rdr_98d06cebc6c4404dad6cfebf36e17830},
  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_veronese_mapping_98d06ceb_v1,
  title = {Veronese mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/veronese-mapping/rdr_98d06cebc6c4404dad6cfebf36e17830/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake