# Low-rank Matrix Recovery With Unknown Correspondence

arXiv: https://arxiv.org/abs/2110.07959 · HTML: https://mlsanity.com/paper/2110.07959/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 80 references that are in the map.
- First posted on arXiv 15 Oct 2021.

## Builds on (most cited first, 28 of 28)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Learning Correspondence from the Cycle-Consistency of Time](https://mlsanity.com/paper/1903.07593/) (2019)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Learning Dense Correspondence via 3D-guided Cycle Consistency](https://mlsanity.com/paper/1604.05383/) (2016)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Proposal Flow](https://mlsanity.com/paper/1511.05065/) (2015)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://mlsanity.com/paper/2006.08141/) (2020)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [DeepPermNet: Visual Permutation Learning](https://mlsanity.com/paper/1704.02729/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Denoising Linear Models with Permuted Data](https://mlsanity.com/paper/1704.07461/) (2017)
- [Linear Regression with Shuffled Labels](https://mlsanity.com/paper/1705.01342/) (2017)
- [Linear Regression without Correspondences via Concave Minimization](https://mlsanity.com/paper/2003.07706/) (2020)
- [Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method](https://mlsanity.com/paper/2003.08093/) (2020)
- [A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Data](https://mlsanity.com/paper/1910.01623/) (2019)
- [A Hypergradient Approach to Robust Regression without Correspondence](https://mlsanity.com/paper/2012.00123/) (2020)
- [The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors](https://mlsanity.com/paper/1909.02496/) (2019)
- [Solving Variational Inequalities with Monotone Operators on Domains Given by Linear Minimization Oracles](https://mlsanity.com/paper/1312.1073/) (2013)
- [Sample-to-Sample Correspondence for Unsupervised Domain Adaptation](https://mlsanity.com/paper/1805.00355/) (2018)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [ROML: A Robust Feature Correspondence Approach for Matching Objects in A Set of Images](https://mlsanity.com/paper/1403.7877/) (2014)
- [Robust approximate linear regression without correspondence](https://mlsanity.com/paper/1906.00273/) (2019)

## Built on by (most cited first, 4 of 4)

- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [z-SignFedAvg: A Unified Stochastic Sign-based Compression for Federated Learning](https://mlsanity.com/paper/2302.02589/) (2023)
- [Optimal Estimator for Linear Regression with Shuffled Labels](https://mlsanity.com/paper/2310.01326/) (2023)
- [Multi-Subspace Matrix Recovery from Permuted Data](https://mlsanity.com/paper/2412.12931/) (2024)

## Abstract (arXiv)

We study a matrix recovery problem with unknown correspondence: given the observation matrix Mo=[A,tilde P B], where tilde P is an unknown permutation matrix, we aim to recover the underlying matrix M=[A,B]. Such problem commonly arises in many applications where heterogeneous data are utilized and the correspondence among them are unknown, e.g., due to privacy concerns. We show that it is possible to recover M via solving a nuclear norm minimization problem under a proper low-rank condition on M, with provable non-asymptotic error bound for the recovery of M. We propose an algorithm, M3O (Matrix recovery via Min-Max Optimization) which recasts this combinatorial problem as a continuous minimax optimization problem and solves it by proximal gradient with a Max-Oracle. M3O can also be applied to a more general scenario where we have missing entries in Mo and multiple groups of data with distinct unknown correspondence. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that M3O achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.