Linear least squares with unordered response variable In the classical linear regression model one considers the equation
$$ y = X \beta + \epsilon.$$
I was wondering whether there are also results when the ordering of the response variable $y$ is not given, i.e. $y$ is not a vector $(y_1, y_2, \dots, y_n)$ but rather a set $\{y_1, y_2, \dots, y_n\}$.
Would there be efficient ways of estimating $\beta$ ? I suppose there also have to be conditions on $X$ that this is even possible in the noiseless case.
 A: Your question seems rather broad and you could specify this more if you need more specific answers. Here are some general observations:
The noiseless case, i.e. $\epsilon = 0$: 
The condition on $X$ is that the pairs $(X_i, Y_{\pi(i)})$ lie on a single hyperplane for some permutation $\pi$ of $1,\ldots, n$.  In dimension 1 this is easy to check, just sort the $X$ and the $Y$. Since you can sort ascending or descending, there is no unique solution unless $\beta$ is zero. In higher dimensions a straightforward attack would be to check linear dependence of the pairs for each possible permutation. Of course this gets cumbersome in practice if $n$ is larger than 9 or  10. Hence an important factor in assessing "efficiency" of the solution is the size of $n$ and the number of factors $p$.
The case with noise:
I think here you really need to specify what you want from a solution and what your criterion for efficiency is. Each permutation of the $Y$ is a standard least squares problem and after solving those you will have (in general) $n!$ different solutions for $\beta$. Depending on your estimation problem, you might want to choose the average of those, or that value of $\beta$ which gives you the lowest estimated $R^2$ or variance of $\epsilon$ or something else entirely. From what you say I do not see a single clear criterion for an estimate of $\beta$.
Anyway, due to the permutations involved, I guess the problem will become quickly harder for growing numbers of $n$.
Normally one does regression either for explanation or prediction. Both seem to be difficult concepts in your setting. Do you mind, explaining why you are interested in this?
