Complex almost-injective intensity measurements have NP-complete consistency

Let F={ΦM}M=2\mathcal{F}=\{\Phi_M\}_{M=2}^\infty be a family of ensembles ΦM={φM;n}n=12MCM\Phi_M=\{\varphi_{M;n}\}_{n=1}^{2M}\subseteq\mathbb{C}^M which yield almost injective intensity measurements and have complex rational entries that can be computed in polynomial time. The consistency conjecture. Then \textscConsistentIntensities[F]\textsc{ConsistentIntensities}[\mathcal{F}] is \NP\NP-complete. This would strengthen the preceding hardness result for the smallest possible almost-injective ensembles in the complex case, paralleling the established result for full spark ensembles with M+1M+1 measurements; the conjectured NP-completeness is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Matthew Fickus, Dustin G. Mixon, Aaron A. Nelson and Yang Wang, “Phase retrieval from very few measurements”, arXiv:1307.7176 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.