Partitioned Least Squares

• URL: http://arxiv.org/abs/2006.16202v2
• Date: Sat, 29 Jun 2024 09:40:27 GMT
• Title: Partitioned Least Squares
• Authors: Roberto Esposito, Mattia Cerrato, Marco Locatelli,
• Abstract summary: We show that the new formulation is not convex and provide two alternative methods to deal with the problem. For the sake of completeness, we provide an alternative branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large.
• Score: 3.372747046563984
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we propose a variant of the linear least squares model allowing practitioners to partition the input features into groups of variables that they require to contribute similarly to the final result. The output allows practitioners to assess the importance of each group and of each variable in the group. We formally show that the new formulation is not convex and provide two alternative methods to deal with the problem: one non-exact method based on an alternating least squares approach; and one exact method based on a reformulation of the problem using an exponential number of sub-problems whose minimum is guaranteed to be the optimal solution. We formally show the correctness of the exact method and also compare the two solutions showing that the exact solution provides better results in a fraction of the time required by the alternating least squares solution (assuming that the number of partitions is small). For the sake of completeness, we also provide an alternative branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large, and a proof of NP-completeness of the optimization problem introduced in this paper.

Related papers

• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  This research presents a method to meet requirements through the minimization objective function of the RPM algorithm. A branch-and-bound (BnB) algorithm is devised, which solely branches over the parameters, thereby boosting convergence rate. Empirical evaluations demonstrate better robustness of the proposed methodology against non-rigid deformation, positional noise, and outliers, when compared with prevailing state-of-the-art transformations.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings [7.6275971668447005]
  We tackle the problem of computing a sequence of rankings with the guarantee of the Pareto-optimal balance between consumers and producers of items. We introduce a novel approach to the above problem by using the Expohedron - a permutahedron whose points represent all exposures of items. We further propose an efficient method by relaxing our optimization problem on the Expohedron's circumscribed $n$-sphere, which significantly improve the running time.
  arXiv  Detail & Related papers  (2024-02-22T05:48:54Z)
• Multiple Convex Objects Image Segmentation via Proximal Alternating Direction Method of Multipliers [2.294014185517203]
  The convex shape prior turns out to be a simple quadratic inequality constraint on the binary indicator function associated with each object. An image segmentation model incorporating convex shape prior into a probability-based method is proposed. Numerical experiments on natural and medical images demonstrate that the proposed method is superior to some existing methods.
  arXiv  Detail & Related papers  (2022-03-22T00:05:19Z)
• Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection [0.0]
  We show that our proposed algorithms can find a locally optimal solution in near linear time. Our algorithms require neither positive nor integer elements in the input set, hence, they are more widely applicable.
  arXiv  Detail & Related papers  (2021-09-10T11:53:34Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  This paper introduces a class of mixed-integer formulations for trained ReLU neural networks. At one extreme, one partition per input recovers the convex hull of a node, i.e., the tightest possible formulation for each node.
  arXiv  Detail & Related papers  (2021-02-08T17:27:34Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Accelerated Sparse Bayesian Learning via Screening Test and Its Applications [0.9916217495995309]
  For a linear system, to find the sparsest solution provided with an over-complete dictionary of features directly is typically NP-hard. We propose sparse Bayesian learning, which uses a parameterized prior to encourage sparsity in solution.
  arXiv  Detail & Related papers  (2020-07-08T10:21:56Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  We propose a robust method to align point sets where there is no prior information about the value of the transformation. Our algorithm does not need regularization on transformation, and thus can handle the situation where there is no prior information about the values of the transformations. Experimental results demonstrate the better robustness of the proposed method over state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-07-05T15:23:33Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  convex mixed-integer programming formulation for non-rigid shape matching. We propose a novel shape deformation model based on an efficient low-dimensional discrete model.
  arXiv  Detail & Related papers  (2020-02-28T09:54:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.