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 of $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:

where $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 = \text{diag}(b)u$ where $u \in \mathbb{C}^n$ is a phase vector, satisfying $|\mathbb{u}_i| = 1$ for $i = 1,\ldots, 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:

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, () -> SCS.Optimizer(verbose=0))
U.value

20×20 Array{Complex{Float64},2}:
       1.0-8.2134e-10im    0.956308-0.292362im    …  -0.998327-0.0578206im 
  0.956308+0.292362im           1.0-2.08589e-9im     -0.937803-0.347167im  
  0.594865+0.803826im      0.803882+0.594789im       -0.547392-0.836877im  
  0.482367+0.87597im       0.717391+0.696671im       -0.430911-0.902395im  
  0.990595+0.136828im      0.987317-0.158763im       -0.981026-0.193875im  
 -0.767393+0.641177im     -0.546408+0.837519im    …   0.803183-0.595733im  
 -0.360777+0.932652im    -0.0723418+0.99738im           0.4141-0.910232im  
 -0.934116+0.356972im     -0.788937+0.614475im        0.953193-0.302363im  
  0.958386-0.285475im       0.83305-0.553198im       -0.973289+0.229583im  
  0.984728+0.174104im      0.992604-0.121401im       -0.973013-0.23075im   
 -0.971014+0.239022im     -0.858708+0.512467im    …    0.98321-0.182478im  
  0.764413+0.644728im      0.919508+0.393073im       -0.725855-0.687848im  
 -0.368793+0.929512im    -0.0809259+0.99672im         0.421921-0.906633im  
  0.982542+0.186044im      0.994004-0.109343im       -0.970141-0.242544im  
  0.999264-0.0383638im     0.944388-0.328835im       -0.999811-0.0194783im 
 -0.543259+0.839566im     -0.274065+0.961711im    …   0.590894-0.806749im  
 -0.793748+0.608247im     -0.581239+0.813733im        0.827589-0.561335im  
  0.962797+0.270228im      0.999734-0.0230644im      -0.945561-0.325445im  
  0.915074+0.403287im      0.992998+0.118133im       -0.890225-0.455522im  
 -0.998327+0.0578206im    -0.937803+0.347167im             1.0-1.04206e-9im

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)])

1

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.5948648860624225 - 0.8038257070596468im 
   0.8038820935447081 - 0.5947886848942043im 
                  1.0 + 0.0im                
   0.9910696887227978 + 0.13334493651765292im
   0.6992556695821882 - 0.7148716727897153im 
  0.05889912727581745 + 0.9982639394499568im 
   0.5350760131895872 + 0.8448039181426285im 
  -0.2687295361522386 + 0.9632156749136732im 
   0.3406377266270483 - 0.9401946283607221im 
   0.7257285896083895 - 0.687981114729916im  
 -0.38549022483145934 + 0.9227119195932125im 
   0.9729706647310437 - 0.2309287456615807im 
   0.5277830280478492 + 0.8493792293814602im 
   0.7340263745336105 - 0.6791209623395849im 
    0.563589145379733 - 0.8260552494900943im 
  0.35169861554292076 + 0.9361132857860703im 
 0.016751728072860756 + 0.9998596799584295im 
   0.7899498077745476 - 0.6131715104250649im 
   0.8685173473463038 - 0.49565877109009165im
  -0.5473920338045287 + 0.836876311845031im  

This page was generated using Literate.jl.