Shuffled Linear Regression via Spectral Matching

• URL: http://arxiv.org/abs/2410.00078v1
• Date: Mon, 30 Sep 2024 16:26:40 GMT
• Title: Shuffled Linear Regression via Spectral Matching
• Authors: Hang Liu, Anna Scaglione,
• Abstract summary: Shuffled linear regression seeks to estimate latent features through a linear transformation. This problem extends traditional least-squares (LS) and Least Absolute Shrinkage and Selection Operator (LASSO) approaches. We propose a spectral matching method that efficiently resolves permutations.
• Score: 6.24954299842136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shuffled linear regression (SLR) seeks to estimate latent features through a linear transformation, complicated by unknown permutations in the measurement dimensions. This problem extends traditional least-squares (LS) and Least Absolute Shrinkage and Selection Operator (LASSO) approaches by jointly estimating the permutation, resulting in shuffled LS and shuffled LASSO formulations. Existing methods, constrained by the combinatorial complexity of permutation recovery, often address small-scale cases with limited measurements. In contrast, we focus on large-scale SLR, particularly suited for environments with abundant measurement samples. We propose a spectral matching method that efficiently resolves permutations by aligning spectral components of the measurement and feature covariances. Rigorous theoretical analyses demonstrate that our method achieves accurate estimates in both shuffled LS and shuffled LASSO settings, given a sufficient number of samples. Furthermore, we extend our approach to address simultaneous pose and correspondence estimation in image registration tasks. Experiments on synthetic datasets and real-world image registration scenarios show that our method outperforms existing algorithms in both estimation accuracy and registration performance.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Verification of Geometric Robustness of Neural Networks via Piecewise Linear Approximation and Lipschitz Optimisation [57.10353686244835]
  We address the problem of verifying neural networks against geometric transformations of the input image, including rotation, scaling, shearing, and translation. The proposed method computes provably sound piecewise linear constraints for the pixel values by using sampling and linear approximations in combination with branch-and-bound Lipschitz. We show that our proposed implementation resolves up to 32% more verification cases than present approaches.
  arXiv  Detail & Related papers  (2024-08-23T15:02:09Z)
• Low-Rank Approximation of Structural Redundancy for Self-Supervised Learning [2.3072402651280517]
  We study the data-generating mechanism for reconstructive SSL to shed light on its effectiveness. With an infinite amount of labeled samples, we provide a sufficient and necessary condition for perfect linear approximation. Motivated by the condition, we propose to approximate the redundant component by a low-rank factorization.
  arXiv  Detail & Related papers  (2024-02-10T04:45:27Z)
• SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning [14.663513734368628]
  We show that the communication complexity of FedLSA scales with the inverse of the desired accuracy. An important finding is that, compared to the existing results for Scaffnew, the sample complexity scales with the inverse of the number of agents.
  arXiv  Detail & Related papers  (2024-02-06T16:06:59Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for non-rigid shapes. We show state-of-the-art results for sparse non-rigid matching on several challenging 3D datasets.
  arXiv  Detail & Related papers  (2023-08-16T14:25:30Z)
• Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning [16.673022545571566]
  We propose a new method for high-dimensional semi-supervised learning problems. It is based on the careful aggregation of the results of a low-dimensional procedure applied to many axis-aligned random projections of the data.
  arXiv  Detail & Related papers  (2023-04-18T17:49:02Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• An Exact Solution Path Algorithm for SLOPE and Quasi-Spherical OSCAR [0.0]
  This study presents a solution path algorithm that provides the complete and exact path of solutions for SLOPE in fine-tuning regularization weights. It also proposes a new design of a regularization sequence $lambda$ for feature clustering, which is called the quasi-spherical and octagonal shrinkage and clustering algorithm for regression ( QS-OSCAR)
  arXiv  Detail & Related papers  (2020-10-29T12:03:22Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• Spatially Adaptive Inference with Stochastic Feature Sampling and Interpolation [72.40827239394565]
  We propose to compute features only at sparsely sampled locations. We then densely reconstruct the feature map with an efficient procedure. The presented network is experimentally shown to save substantial computation while maintaining accuracy over a variety of computer vision tasks.
  arXiv  Detail & Related papers  (2020-03-19T15:36:31Z)
• Ensemble Slice Sampling: Parallel, black-box and gradient-free inference for correlated & multimodal distributions [0.0]
  Slice Sampling has emerged as a powerful Markov Chain Monte Carlo algorithm that adapts to the characteristics of the target distribution with minimal hand-tuning. This paper introduces Ensemble Slice Sampling (ESS), a new class of algorithms that bypasses such difficulties by adaptively tuning the initial length scale. These affine-invariant algorithms are trivial to construct, require no hand-tuning, and can easily be implemented in parallel computing environments.
  arXiv  Detail & Related papers  (2020-02-14T19:00:12Z)

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.