All of the examples can be found in Jupyter notebook form here.

Phase recovery using MaxCut

In this example, we relax the phase retrieval problem similar to the classical MaxCut semidefinite program and recover the phase of the signal given the magnitude of the linear measurements.

Phase recovery has wide applications such as in X-ray and crystallography imaging, diffraction imaging or microscopy and audio signal processing. In all these applications, the detectors cannot measure the phase of the incoming wave and only record its amplitude i.e complex measurements of a signal $x \in \mathbb{C}^p$ are obtained from a linear injective operator A, but we can only measure the magnitude vector Ax, not the phase fo Ax.

Recovering the phase of $Ax$ from $|Ax|$ is a nonconvex optimization problem. Using results from this paper, the problem can be relaxed to a (complex) semidefinite program (complex SDP).

The original reprsentation of the problem is as follows:

find $x$

such that $|Ax| = b$

where $x \in \mathbb{C}^p$, $A \in \mathbb{C}^{n \times p}$ and $b \in \mathbb{R}^n$.

In this example, the problem is to find the phase of Ax given the value |Ax|. Given a linear operator $A$ and a vector $b= |Ax|$ of measured amplitudes, in the noiseless case, we can write Ax = diag(b)u where $u \in \mathbb{C}^n$ is a phase vector, satisfying |$\mathbb{u}_i$| = 1 for i = 1,. . . , n.

We relax this problem as Complex Semidefinite Programming.

Relaxed Problem similar to MaxCut

Define the positive semidefinite hermitian matrix $M = \text{diag}(b) (I - A A^*) \text{diag}(b)$. The problem is:

            minimize < U,M >
            subject to
            diag(U) = 1
            U in :HermitianSemiDefinite

Here the variable $U$ must be hermitian ($U \in \mathbb{H}_n $), and we have a solution to the phase recovery problem if $U = u u^*$ has rank one. Otherwise, the leading singular vector of $U$ can be used to approximate the solution.

using Convex, SCS, LinearAlgebra
if VERSION < v"1.2.0-DEV.0"
    (I::UniformScaling)(n::Integer) = Diagonal(fill(I.λ, n))
     LinearAlgebra.diagm(v::AbstractVector) = diagm(0 => v)
end

n = 20
p = 2
A = rand(n,p) + im*randn(n,p)
x = rand(p) + im*randn(p)
b = abs.(A*x) + rand(n)

M = diagm(b)*(I(n)-A*A')*diagm(b)
U = ComplexVariable(n,n)
objective = inner_product(U,M)
c1 = diag(U) == 1
c2 = U in :SDP
p = minimize(objective,c1,c2)
solve!(p, SCSSolver(verbose=0))
U.value

20×20 Array{Complex{Float64},2}:
       1.0+9.18807e-9im    0.956311-0.292363im    …   -0.99833-0.0578207im 
  0.956311+0.292363im           1.0+3.90564e-8im     -0.937806-0.347168im  
  0.594867+0.803828im      0.803885+0.594791im       -0.547394-0.836879im  
  0.482368+0.875972im      0.717393+0.696673im       -0.430912-0.902397im  
  0.990598+0.136828im       0.98732-0.158764im       -0.981029-0.193876im  
 -0.767396+0.641179im      -0.54641+0.837522im    …   0.803185-0.595735im  
 -0.360778+0.932655im     -0.072342+0.997383im        0.414101-0.910234im  
 -0.934118+0.356973im     -0.788939+0.614476im        0.953195-0.302364im  
  0.958389-0.285476im      0.833052-0.5532im         -0.973292+0.229584im  
   0.98473+0.174104im      0.992607-0.121401im       -0.973016-0.23075im   
 -0.971017+0.239023im      -0.85871+0.512468im    …   0.983213-0.182478im  
  0.764415+0.644729im       0.91951+0.393074im       -0.725857-0.68785im   
 -0.368794+0.929514im    -0.0809261+0.996723im        0.421922-0.906635im  
  0.982544+0.186045im      0.994007-0.109343im       -0.970143-0.242545im  
  0.999267-0.0383639im      0.94439-0.328836im       -0.999813-0.0194784im 
 -0.543261+0.839568im     -0.274066+0.961714im    …   0.590896-0.806752im  
  -0.79375+0.608249im     -0.581241+0.813736im        0.827591-0.561336im  
  0.962799+0.270229im      0.999737-0.0230644im      -0.945564-0.325446im  
  0.915077+0.403288im      0.993001+0.118134im       -0.890227-0.455523im  
  -0.99833+0.0578206im    -0.937806+0.347168im             1.0+6.17005e-8im

Verify if the rank of $U$ is 1:

B, C = eigen(U.value);
length([e for e in B if(abs(real(e))>1e-4)])

Decompose $U = uu^*$ where $u$ is the phase of $Ax$

u = C[:,1];
for i in 1:n
    u[i] = u[i]/abs(u[i])
end
u

20-element Array{Complex{Float64},1}:
   0.9563076630823117 - 0.29236219579495537im 
                  1.0 + 0.0im                 
   0.8038820902537878 + 0.5947886893420224im  
   0.7173911217715979 + 0.6966706383961422im  
   0.9873166925580649 - 0.15876318400751369im 
  -0.5464081389825624 + 0.8375190419647859im  
 -0.07234181122338455 + 0.9973798987090727im  
  -0.7889366580089129 + 0.6144745313271559im  
   0.8330496841937677 - 0.5531981775680971im  
   0.9926035973551424 - 0.12140057049960741im 
  -0.8587073010669556 + 0.5124663609392376im  
   0.9195075025161856 + 0.3930724523754451im  
 -0.08092582565354957 + 0.9967201265863409im  
   0.9940041230626339 - 0.10934259615760034im 
   0.9443875273058244 - 0.3288346062524298im  
 -0.27406539493892057 + 0.9617110581130768im  
  -0.5812388343737598 + 0.8137330135958801im  
   0.9997339809910151 - 0.023064415272377632im
   0.9929977756168094 + 0.11813305049844637im 
  -0.9378032256618035 + 0.3471672650730715im

This page was generated using Literate.jl.