Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2512.11642 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909958649413632 |
|---|---|
| author | Gilles, Timm |
| author_facet | Gilles, Timm |
| contents | We study the recovery of low-rank Hermitian matrices from rank-one measurements obtained by uniform sampling from complex projective 3-designs, using nuclear-norm minimization. This framework includes phase retrieval as a special case via the PhaseLift method. In general, complex projective $t$-designs provide a practical means of partially derandomizing Gaussian measurement models. While near-optimal recovery guarantees are known for $4$-designs, and it is known that $2$-designs do not permit recovery with a subquadratic number of measurements, the case of $3$-designs has remained open. In this work, we close this gap by establishing recovery guarantees for (exact and approximate) $3$-designs that parallel the best-known results for $4$-designs. In particular, we derive bounds on the number of measurements sufficient for stable and robust low-rank recovery via nuclear-norm minimization. Our results are especially relevant in practice, as explicit constructions of $4$-designs are significantly more challenging than those of $3$-designs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11642 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stable low-rank matrix recovery from 3-designs Gilles, Timm Information Theory 94A20, 94A12, 60B20, 90C25 We study the recovery of low-rank Hermitian matrices from rank-one measurements obtained by uniform sampling from complex projective 3-designs, using nuclear-norm minimization. This framework includes phase retrieval as a special case via the PhaseLift method. In general, complex projective $t$-designs provide a practical means of partially derandomizing Gaussian measurement models. While near-optimal recovery guarantees are known for $4$-designs, and it is known that $2$-designs do not permit recovery with a subquadratic number of measurements, the case of $3$-designs has remained open. In this work, we close this gap by establishing recovery guarantees for (exact and approximate) $3$-designs that parallel the best-known results for $4$-designs. In particular, we derive bounds on the number of measurements sufficient for stable and robust low-rank recovery via nuclear-norm minimization. Our results are especially relevant in practice, as explicit constructions of $4$-designs are significantly more challenging than those of $3$-designs. |
| title | Stable low-rank matrix recovery from 3-designs |
| topic | Information Theory 94A20, 94A12, 60B20, 90C25 |
| url | https://arxiv.org/abs/2512.11642 |