Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation
In this paper, we study the problem of sparse mixed linear regression on an
unlabeled dataset that is generated from linear measurements from two different
regression parameter vectors. Since the data is unlabeled, our task is not only
to figure out a good approximation of the regression parameter vectors but also
to label the dataset correctly. In its original form, this problem is NP-hard.
The most popular algorithms to solve this problem (such as
Expectation-Maximization) have a tendency to stuck at local minima. We provide
a novel invex relaxation for this intractable problem which leads to a solution
with provable theoretical guarantees. This relaxation enables exact recovery of
data labels. Furthermore, we recover a close approximation of the regression
parameter vectors which match the true parameter vectors in support and sign.
Our formulation uses a carefully constructed primal dual witnesses framework
for the invex problem. Furthermore, we show that the sample complexity of our
method is only logarithmic in terms of the dimension of the regression
parameter vectors.