2023/10/02 by Hang Zhang, Ping Li, Zhang, Hang +1
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Blind Source Separation Techniques #Electrical and Bioimpedance Tomography
paper · pdf · doi:10.48550/arxiv.2310.01326
This paper considers the task of linear regression with shuffled labels, i.e., \mathbf Y = \mathbf Π\mathbf X \mathbf B + \mathbf W, where \mathbf Y ∈ \mathbb Rn× m, \mathbf Pi ∈ \mathbb Rn× n, \mathbf X∈ \mathbb Rn× p, \mathbf B ∈ \mathbb Rp× m, and \mathbf W∈ \mathbb Rn× m, respectively, represent the sensing results, (unknown or missing) corresponding information, sensing matrix, signal of interest, and additive sensing noise. Given the observation \mathbf Y and sensing matrix \mathbf X, we propose a one-step estimator to reconstruct (\mathbf Π, \mathbf B). From the computational perspective, our estimator's complexity is O(n3 + np2m), which is no greater than the maximum complexity of a linear assignment algorithm (e.g., O(n3)) and a least square algorithm (e.g., O(np2 m)). From the statistical perspective, we divide the minimum snr requirement into four regimes, e.g., unknown, hard, medium, and easy regimes; and present sufficient conditions for the correct permutation recovery under each regime: (i) snr ≥ Ω(1) in the easy regime; (ii) snr ≥ Ω(log n) in the medium regime; and (iii) snr ≥ Ω((log n)c0⋅ n^c1/srank(\mathbf B)) in the hard regime (c0, c1 are some positive constants and srank(\mathbf B) denotes the stable rank of \mathbf B). In the end, we also provide numerical experiments to confirm the above claims.