An Algebraic-Geometric Approach for Linear Regression Without Correspondences

DOI10.1109/TIT.2020.2977166zbMATH Open1446.62202arXiv1810.05440OpenAlexW3007679270MaRDI QIDQ5124491FDOQ5124491

Authors: Liangzu Peng, Aldo Conca, Laurent Kneip, Yuanming Shi, Hayoung Choi, Manolis C. Tsakiris 

Publication date: 29 September 2020

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Linear regression without correspondences is the problem of performing a linear regression fit to a dataset for which the correspondences between the independent samples and the observations are unknown. Such a problem naturally arises in diverse domains such as computer vision, data mining, communications and biology. In its simplest form, it is tantamount to solving a linear system of equations, for which the entries of the right hand side vector have been permuted. This type of data corruption renders the linear regression task considerably harder, even in the absence of other corruptions, such as noise, outliers or missing entries. Existing methods are either applicable only to noiseless data or they are very sensitive to initialization or they work only for partially shuffled data. In this paper we address these issues via an algebraic geometric approach, which uses symmetric polynomials to extract permutation-invariant constraints that the parameters $x{i}^{\ast }inR{e}^n$ of the linear regression model must satisfy. This naturally leads to a polynomial system of $n$ equations in $n$ unknowns, which contains $x{i}^{\ast }$ in its root locus. Using the machinery of algebraic geometry we prove that as long as the independent samples are generic, this polynomial system is always consistent with at most $n!$ complex roots, regardless of any type of corruption inflicted on the observations. The algorithmic implication of this fact is that one can always solve this polynomial system and use its most suitable root as initialization to the Expectation Maximization algorithm. To the best of our knowledge, the resulting method is the first working solution for small values of $n$ able to handle thousands of fully shuffled noisy observations in milliseconds.

Full work available at URL: https://arxiv.org/abs/1810.05440

Recommendations

• A GEOMETRIC CHARACTERIZATION OF LINEAR REGRESSION
• The geometry of linear regression with correlated errors
• Linear programming and \(\ell _ 1\) regression: A geometric interpretation
• scientific article; zbMATH DE number 813685
• A geometric approach to the linear modelling
• scientific article; zbMATH DE number 772781
• scientific article; zbMATH DE number 509235

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Linear regression; mixed models (62J05) Algebraic statistics (62R01)

Cited In (8)

• Recovery from Power Sums
• Finding explicit solutions for linear regression without correspondences based on rearrangement inequality
• Title not available (Why is that?)
• Linear regression with mismatched data: a provably optimal local search algorithm
• Combinatorial reduction of set functions and matroid permutations through minor invertible product assignment
• Matrix recovery from permutations
• Linear regression with partially mismatched data: local search with theoretical guarantees
• Homomorphic sensing of subspace arrangements

Uses Software

• Bertini
• CAP3
• SoftPOSIT
• Polyjam

This page was built for publication: An Algebraic-Geometric Approach for Linear Regression Without Correspondences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124491)