TY - JOUR

T1 - An Algebraic-Geometric Approach for Linear Regression without Correspondences

AU - Tsakiris, Manolis C.

AU - Peng, Liangzu

AU - Conca, Aldo

AU - Kneip, Laurent

AU - Shi, Yuanming

AU - Choi, Hayoung

N1 - Publisher Copyright:
© 1963-2012 IEEE.

PY - 2020/8

Y1 - 2020/8

N2 - 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 xi {*} in mathbb {R} {text {n}} of the linear regression model must satisfy. This naturally leads to a polynomial system of n equations in n unknowns, which contains xi {*} 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.

AB - 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 xi {*} in mathbb {R} {text {n}} of the linear regression model must satisfy. This naturally leads to a polynomial system of n equations in n unknowns, which contains xi {*} 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.

KW - algebraic geometry

KW - expectation maximization

KW - homomorphic sensing

KW - linear regression with shuffled data

KW - Linear regression without correspondences

KW - shuffled linear regression

KW - unlabeled sensing

UR - http://www.scopus.com/inward/record.url?scp=85088506686&partnerID=8YFLogxK

U2 - 10.1109/TIT.2020.2977166

DO - 10.1109/TIT.2020.2977166

M3 - Article

AN - SCOPUS:85088506686

SN - 0018-9448

VL - 66

SP - 5130

EP - 5144

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 8

M1 - 9018107

ER -