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.

In [101]:
using Convex
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)*(eye(n)-A*ctranspose(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)
U.value
(size(coeff),size(var)) = ((40,40),(40,40))
----------------------------------------------------------------------------
	SCS v1.1.8 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012-2015
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 3181
eps = 1.00e-04, alpha = 1.80, max_iters = 20000, normalize = 1, scale = 5.00
Variables n = 801, constraints m = 1641
Cones:	primal zero / dual free vars: 821
	sd vars: 820, sd blks: 1
Setup time: 1.03e-03s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0|      inf       inf      -nan      -inf      -inf       inf  1.17e-03 
   100|      inf       inf      -nan      -inf      -inf       inf  1.48e-01 
   200|      inf       inf      -nan      -inf      -inf       inf  2.76e-01 
   300|      inf       inf      -nan      -inf      -inf       inf  4.01e-01 
   400| 5.94e-02  1.47e-03  1.06e-05 -1.33e+03 -1.33e+03  2.40e-17  5.62e-01 
   500| 1.22e-02  2.87e-04  2.14e-06 -1.33e+03 -1.33e+03  8.67e-18  6.90e-01 
   600| 2.64e-03  6.29e-05  4.60e-07 -1.33e+03 -1.33e+03  7.28e-17  8.22e-01 
   700| 5.73e-04  1.37e-05  9.98e-08 -1.33e+03 -1.33e+03  7.30e-17  9.63e-01 
   800| 1.25e-04  2.98e-06  2.17e-08 -1.33e+03 -1.33e+03  7.73e-18  1.09e+00 
   820| 9.18e-05  2.20e-06  1.60e-08 -1.33e+03 -1.33e+03  2.45e-17  1.11e+00 
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 1.11e+00s
	Lin-sys: nnz in L factor: 6763, avg solve time: 5.92e-05s
	Cones: avg projection time: 1.26e-03s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 6.5244e-09, dist(y, K*) = 1.8637e-09, s'y/m = -5.3273e-10
|Ax + s - b|_2 / (1 + |b|_2) = 9.1773e-05
|A'y + c|_2 / (1 + |c|_2) = 2.1952e-06
|c'x + b'y| / (1 + |c'x| + |b'y|) = 1.6034e-08
----------------------------------------------------------------------------
c'x = -1326.1472, -b'y = -1326.1471
============================================================================
Out[101]:
20×20 Array{Complex{Float64},2}:
 0.999998+1.49475e-15im        …           0.641021-0.766111im 
          0.446918-0.760165im             -0.279396-0.844012im 
          0.540963+0.840695im              0.991945+0.124332im 
          0.310127-0.919005im             -0.498066-0.83538im  
          0.601155+0.79323im               0.997432+0.0489258im
          0.318761+0.886608im  …           0.899099+0.324567im 
         -0.273286-0.917372im             -0.866077-0.384836im 
          0.940279-0.213429im              0.435288-0.868812im 
          -0.72136-0.548241im             -0.863905+0.207653im 
          0.535909+0.814248im              0.975065+0.118254im 
          0.766546+0.641349im  …           0.981572-0.175106im 
          0.858843-0.134508im               0.44869-0.767066im 
          0.491533-0.848226im             -0.335281-0.929426im 
          0.939298+0.337107im              0.862322-0.505741im 
         -0.289044-0.902153im             -0.862436-0.361781im 
          0.872244+0.474994im  …           0.923208-0.369149im 
          0.532716+0.829509im              0.984631+0.122242im 
         -0.446504-0.715904im              -0.81144-0.10799im  
          0.876944+0.475247im              0.927712-0.364238im 
          0.641021+0.766111im     0.999993+3.07926e-15im       
In [107]:
# Verify if the rank of U is 1
B, C = eig(U.value);
println(length([e for e in B if(abs(real(e))>1e-4)]))
#Decompose U = uu*
# u is the phase of Ax
u = C[:,1];
for i in 1:n
    u[i] = u[i]/abs(u[i])
end
u
2
Out[107]:
20-element Array{Complex{Float64},1}:
  0.642427-0.766347im 
 -0.320032-0.947407im 
  0.992174+0.124859im 
 -0.513966-0.857811im 
  0.998852+0.0479087im
  0.942305+0.334756im 
 -0.912508-0.40906im  
  0.446383-0.894842im 
 -0.974714+0.223458im 
  0.993151+0.116834im 
    0.9847-0.174256im 
  0.498451-0.866918im 
 -0.342385-0.93956im  
   0.86251-0.506039im 
 -0.920369-0.391052im 
   0.92876-0.370682im 
  0.992626+0.121218im 
  -0.98923-0.146366im 
   0.93096-0.365121im 
       1.0+0.0im