Homomorphic Sensing of Subspace Arrangements
arXiv:2006.05158 · doi:10.1016/j.acha.2021.06.008
Abstract
Homomorphic sensing is a recent algebraic-geometric framework that studies the unique recovery of points in a linear subspace from their images under a given collection of linear maps. It has been successful in interpreting such a recovery in the case of permutations composed by coordinate projections, an important instance in applications known as unlabeled sensing, which models data that are out of order and have missing values. In this paper, we provide tighter and simpler conditions that guarantee the unique recovery for the single-subspace case, extend the result to the case of a subspace arrangement, and show that the unique recovery in a single subspace is locally stable under noise. We specialize our results to several examples of homomorphic sensing such as real phase retrieval and unlabeled sensing. In so doing, in a unified way, we obtain conditions that guarantee the unique recovery for those examples, typically known via diverse techniques in the literature, as well as novel conditions for sparse and unsigned versions of unlabeled sensing. Similarly, our noise result also implies that the unique recovery in unlabeled sensing is locally stable.
arXiv comment18 pages
References in corpus (10)
- An algebraic characterization of injectivity in phase retrieval
- Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
- Signal Recovery from Unlabeled Samples
- Algebraic Clustering of Affine Subspaces
- Linear Regression without Correspondences via Concave Minimization
- Permutations Unlabeled beyond Sampling Unknown
- New Conditions for Sparse Phase Retrieval
- Homomorphic Sensing
- Estimation in exponential family Regression based on linked data contaminated by mismatch error
- The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors