Minimum linear measurements for uniform recovery of real low-rank matrices
For integers $d \ge 2$ and $1 \le r \le \lfloor d/2 \rfloor$ let $\mu_{\mathbb{R}}(d,r)$ be the least $m$ for which there are $A_1, \dots, A_m \in \mathbb{R}^{d \times d}$ such that the linear map $$\mathcal{A}(X) = \bigl(\operatorname{tr}(A_1^{\mathsf T} X), \dots, \operatorname{tr}(A_m^{\mathsf T} X)\bigr)$$ is injective on the real $d \times d$ matrices of rank at most $r$: any two such matrices with the same measurements are equal. Equivalently, the kernel of $\mathcal{A}$ contains no nonzero matrix of rank at most $2r$ (Eldar, Needell and Plan). Eldar, Needell and Plan showed that $4dr - 4r^2$ Gaussian measurement matrices give an injective map with probability one, and conjectured that fewer never suffice. Xu proved the complex analogue of this conjecture, and proved it over $\mathbb{R}$ when $d = 2^k + r$ for a positive integer $k$ or $d = 2r + 1$. He also found eleven real $4 \times 4$ measurement matrices and proved them injective on the matrices of rank at most one, so $\mu_{\mathbb{R}}(4,1) \le 11 < 4dr - 4r^2 = 12$.
Problem. Determine $\mu_{\mathbb{R}}(d,r)$ for all integers $d \ge 2$ and $1 \le r \le \lfloor d/2 \rfloor$.
Source: Xu (2018; arXiv 2015), Problem 1, over ℝ; restated by Xu (2026), Problem 5.1 and Remark 5.6. Eldar, Needell and Plan (2012) conjectured the value 4dr − 4r².
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- AG
- Keywords
- determinantal varieties, linear measurements, low-rank matrix recovery, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{xu2018,
author = {Xu, Zhiqiang},
title = {The minimal measurement number for low-rank matrix recovery},
journal = {Appl. Comput. Harmon. Anal.},
volume = {44},
number = {2},
year = {2018},
pages = {497--508},
doi = {10.1016/j.acha.2017.01.005},
eprint = {1505.07204},
archivePrefix = {arXiv},
}
@article{xu2026,
author = {Xu, Zhiqiang},
title = {Signal Recovery on Algebraic Varieties Using Linear Samples},
journal = {Acta Math. Sin. (Engl. Ser.)},
volume = {42},
number = {3},
year = {2026},
pages = {740--754},
doi = {10.1007/s10114-026-5299-y},
eprint = {2506.17572},
archivePrefix = {arXiv},
}
@article{eldar2012,
author = {Eldar, Yonina C. and Needell, Deanna and Plan, Yaniv},
title = {Uniqueness conditions for low-rank matrix recovery},
journal = {Appl. Comput. Harmon. Anal.},
volume = {33},
number = {2},
year = {2012},
pages = {309--314},
doi = {10.1016/j.acha.2012.04.002},
eprint = {1103.5479},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra17,
author = {Townsend, Alex},
title = {{RA-17}: Minimum linear measurements for uniform recovery of real low-rank matrices},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RA-17/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Resolution claims
This manuscript studies the minimum number $\mu_{\mathbb R}(d,r)$ of real linear measurements that are injective on real $d\times d$ matrices of rank at most $r$. Its main result is an exact solution of a topological relaxation: one measurement below the complex generic count $4dr-4r^2$, a continuous odd nonvanishing map on the low-rank unit link exists if and only if the …
This manuscript studies the minimum number $\mu_{\mathbb R}(d,r)$ of real linear measurements that are injective on all real $d\times d$ matrices of rank at most $r$. The main exact result established here is $\mu_{\mathbb R}(4,1)=11$: a Grassmannian characteristic-class obstruction excludes ten measurements, and exact rational computations confirm that Xu's eleven measurements are injective, both for the matrices printed in his …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-09 | Open → Partially resolved | The registry's curators | Exact Cases and Bounds v1 recorded from OpenProblemsInNLA @ eb7c9d6, writeup/RA17_exact_cases_and_bounds.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00174, "Minimum linear measurements for uniform recovery of real low-rank matrices", clopen.solutions.