Proposition 4.2, p. 12 — Φ(X) = diag(b)⁻¹AXA*diag(b)⁻¹ is a bijection from the PhaseLift feasible set onto the PhaseCutMod feasible set
ProvedPhaseCut.Tight.proposition_4_2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1phase-retrievalphasecutphaseliftsemidefinite-programming
Let and . Assume that
- for ;
- is injective;
- problem (1) has a solution, i.e. there is with .
Then the map
is a bijection from the feasible set of PhaseLift, , onto the feasible set of PhaseCutMod, , where .
This bijection is the core of the equivalence between PhaseLift and the modified MaxCut-type relaxation PhaseCutMod: combined with the fact that preserves the trace objective and the rank, it transfers tightness from PhaseLift to PhaseCutMod (Corollary 4.3).
Formalization Note "A bijection between the feasible points of PhaseCutMod and those of PhaseLift" is stated as Set.BijOn Φ (PhaseLift feasible) (PhaseCutMod feasible): maps the first set into the second, injectively, and onto it. is defined on all complex matrices.
Preamble
import Mathlib import Definitions.Def_PhaseCut_Tight_Defs
Formal statement
namespace PhaseCut.Tight
open Matrix
open scoped ComplexOrder
/-- Proposition 4.2, p. 12: if `bᵢ ≠ 0` for all `i`, `A` is injective and (1) has a solution, then
`Φ(X) = diag(b)⁻¹AXA*diag(b)⁻¹` maps the feasible set of PhaseLift bijectively onto the feasible
set of PhaseCutMod. -/
theorem proposition_4_2 {n p : ℕ} (A : Matrix (Fin n) (Fin p) ℂ) (b : Fin n → ℝ)
(hb : ∀ i, b i ≠ 0) (hA : Function.Injective A.mulVec) (hsol : IsSolvable A b) :
Set.BijOn (Phi A b) (phaseLiftFeasible A b) (phaseCutModFeasible A b) := by sorry
end PhaseCut.Tight
Source
Waldspurger, d'Aspremont & Mallat, arXiv:1206.0102v3, Proposition 4.2, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.