Partitioned Least Squares

  • 2020-06-29 17:10:32
  • Roberto Esposito, Mattia Cerrato, Marco Locatelli
  • 1

Abstract

In this paper we propose a variant of the linear least squares model allowingpractitioners to partition the input features into groups of variables thatthey require to contribute similarly to the final result. The output allowspractitioners to assess the importance of each group and of each variable inthe group. We formally show that the new formulation is not convex and providetwo alternative methods to deal with the problem: one non-exact method based onan alternating least squares approach; and one exact method based on areformulation of the problem using an exponential number of sub-problems whoseminimum is guaranteed to be the optimal solution. We formally show thecorrectness of the exact method and also compare the two solutions showing thatthe exact solution provides better results in a fraction of the time requiredby the alternating least squares solution (assuming that the number ofpartitions is small). For the sake of completeness, we also provide analternative branch and bound algorithm that can be used in place of the exactmethod when the number of partitions is too large, and a proof ofNP-completeness of the optimization problem introduced in this paper.

 

Quick Read (beta)

loading the full paper ...