Reconstruction of information hidden in vector signal phases does not lose its relevance. Sets of vectors iin1 , called frames, in a space C m ( R m ) can be used for theoretical research of phase retrieval. The article shows that phase retrieval is equivalent to phaseless reconstruction. Examples are considered in R m and C m , for which sets of vectors i in1 that simultaneously carry out phase retrieval and phaseless reconstruction are constructed. A search of the fast algorithms for phaseless signal reconstruction is topical now. The main property of frames, which makes them so useful in applied tasks, is their redundancy. A well-chosen frame can provide numerical stability for signal recovery and obtaining important characteristics of the signal [1]. A family of frames recovers the signal by absolute values of frame coefficients in polynomial time. It is shown that in the real case under certain conditions a generic frame consisting of (2m-1)-vectors can recover the signal without phases. The similar result was obtained in the complex space for (4m-2)-vectors. Along with the "phaseless reconstruction", another version of the discrete phase problem statement - "phase retrieval" - is considered. The issue of their equivalence is raised and partially resolved. The present work continues this line of research and gives examples of signal recovery in small-dimension spaces.
and amplitudes of measurements proves m v v, ui
i1 insuperable in signal reconstruction [1, P. 280], [4, P.281].
In recent years, significant amount of works has been devoted to solution of the following task: to construct such systems of "measuring" vectors Ф i in1 that allow recovering a signal v V by a set of real numbers v, i .
Such task has no decision in the ONB class.
The main problem set in [
We have proved that exact recovery of the signal (to the unimodular multiplier) is theoretically possible if complete redundant systems are used as a representation system [2, P. 354]. Frames are such redundant systems.
In 2006, Balan/Casazza/Edidin [
Let m be a space R m or C m .
Definition 1. A family of vectors i i1 is called a frame of a Hilbert space m if there are such constants 0 < A ≤ B < n ∞ that for all x H m the following inequalities are achieved: 2 n A || x || 2 x, f i B || x || 2 .
i1
A and B are called frame bounds. The greatest of the lower bounds is called the optimum lower bound, and the smallest of the upper bounds is the optimum upper bound. If A=B, than the frame is called A-tight and if A=B=1, it is called a Parseval-Steklov fra mThee. numbers x, i in1 are called frame coefficients.
If all frame elements have the same norm than such frames are called uniform ones.
In the finite-dimensional space the notion of a frame is equivalent to the notion of completeness of a system, that
is to the equality span{ i }i1 H m [
n Definition 2. Let i in1 be a frame. The linear mapping:
T : H m H n , T ( x) x, i in1 is called an analysis operator.
Definition 3. The linear mapping: n T * : H n H m , T * (ci in1 ) c
i i i1 is called a synthesis operator.
The composition of T and T * defines a frame operator, which is a positive, self-conjugate reversible operator: n S T *T : H m H m : Sx T *Tx x, i i .
i1 It provides the exact formula for reconstruction:
n x x, i S 1 i .
i1 Definition 4. A family of vectors i i1 is a uniform equiangular tight frame if
n 3rd International conference “Information Technology and Nanotechnology 2017” ______ Mathematical Modeling / А.А. Kuleshova, E.A. Shchelokov 1) 0 : || i || i 1, n ; 2) c 0 : for any pair of frame vectors j and k , j≠k, we have: j , k c.
It is known that there is an upper bound for a number of vectors in the uniform equiangular tight frame i i1 on the
mn
Definition 5. The frame i in1 is called generic if i in1 L U , where U is the Zariski open set and U Gr (m, n) .
Theorem 1 [
Let us consider { i i*u}in1 as vectors of the space R 2m . Let S (u) : spanR { i i*u}in1 . The following statements are equivalent: (a) A is injective. (b) dim S (u) 2n 1 for every u C m \ {0} . (c) S (u) spanR {iu} for every u C m \ {0} .
Definition 6. The family of vectors i i1 in m has the complement property if for any I {1, ... , n}, either n { i }iI , or { i }iI C is complete in m [10].
Definition 7. The family of vectors i in1 R m is called a set with a full spark, if every its subset of m vectors is complete in R m [10].
Lemma 1. Every set with the full spark i i1 in R m with n 2m 1 satisfies the complement property.
n
PBryodoeff.iLnietti'osnasosfutmhee ftuhlel csopnatrrka,rfyr:otmhetrheisisitsufochlloSwst{h1a,t.., nS}thmatn1eiathnedr {SCi }iSm no1r, {thait}iisSnC ar2emnot2c,owmhpilcehtecionntRramdi.cts the condition.
Theorem 2. In the real case if i i1 in R m and n 2m 2 , then mapping A is not injective.
n If n 2m 1, then mapping A is injective if and only if when i i1 is a full spark. n
Proof. If n 2m 2 , then the set {1,.., n} can be divided into sets S and S C such that the cardinality of each would not exceed m 1. None of the sets { i }iS , { i }iSC can be complete.
If n 2m 1 and i in1 is a full spark, then the injectivity of A follows from lemma 1 and theorem 1.
And vice-versa, if A is injective, then i in1 is an alternatively full family. Let's take an arbitrary subset S {1,.., n} with S m . Then S C m 1 and { i }iSC can’t be full. Therefore, { i }iS is full, and i in1 is a full spark.
The exact minimum bound is unknown for the complex case. Besides, in the real case there is a simple direct
method for checking infectivity of the mapping A for the corresponding frame [
Theorem 3 [
m(m 1) (a) If H R m , n and i in1 is a generic frame, the nonlinear map P is injective. Then the vector x H 2 can be reconstructed (up to a sign) from the set {| x, i |}in1 of absolute values of the frame coefficients in a polynomial number (O(m 6 )) of steps.
(b) If H C m , n m 2 and i in1 is a generic frame, the nonlinear map P is injective. Then the vector x H can be reconstructed (up to multiplication by a root of unity) from the set {| x, i |}in1 of absolute values of the frame coefficients in a polynomial number (O(m 6 )) of steps.
Let x (a1 , a2 ,..., am ) and y (b1 , b2 ,..., bm ) be vectors in a space m .
Definition 1: For the phase of number z C m , we take the value of the angle ph zi 2k , k Z , defining the deviation of the radius vector of the point on the plane, corresponding to z C m , from the real axis in C m . In the real case, the phase in R m is equal to 0 or .
We shall say that x, y have the same phases if: (Respectively,
{Pi }in1 does phase retrieval).
Mathematical Modeling / А.А. Kuleshova, E.A. Shchelokov
ph ai ph bi , i 1,2,..., m .
Definition 2. Let i in1 be a family of vectors in m (respectively, {Pi }in1 be a family of projections on m ) satisfying the following property: for every x, y the following condition is satisfied:
x, i y, i , for all i 1,2,..., n .
|| Pi x |||| Pi y || , for all i 1,2,..., n). . 1) If there is a 1 such that x and y have the same phases, one can say i in1 does phase retrieval (respectively, 2) If there is a 1 such that x y , one can say i i1 does phaseless reconstruction. (Respectively, {Pi }in1 does n either { i }iI , or { i }iI C is complete in m .
If { i }i1 retrieves phases in m then span{ i }i1 m . This means that { i }i1 is a frame in the space m .
n n n Otherwise, there exists 0 x m such that x, i y, i 0 , i 1,2,..., n, while phases of vectors x and 0 are not the same.
If x (a1 , a2 ,..., am ) and y (b1 , b2 ,..., bm ) have the same phases then ai 0 if and only if bi 0 , for the phase of 0 is not determined.
Theorem 1. Let i in1 be a set of vectors in R m . The mapping A : R m /{1} R n (n m) is defined by
, i 1,.., n . If i in1does phaseless reconstruction, then it has a complement property. In the real case these concepts are equivalent.
Proof. () Assume that fails the complement property. Then there exists I {1,.., n} such that neither { i }iI , nor { i }iI C is complete in R m .
We choose nonzero vectors u, v Rm such that u, i 0 for all i I and v, i 0 for all i I C . For every i we then have: u v, i
u, i 2 2 2 2 u, i 2 ________ v, i v, i 2 u, i 2 v, i 2
for every i , and A(u v) A(u v) . Moreover, since u and v are nonzero by assumption, then u v (u v) . Thus there is no phaseless reconstruction.
() Assume that i i1 fails phaseless reconstruction. That means there exist vectors x, y R m n such that x y and A( x) A( y) . Take I : {i : x, i
y, i } .
We have: x y, i 0 for every i I . Otherwise if i I C , we have x, i y, i and then x y, i 0 . According to the assumption, x y , therefore x y 0 and x y 0 . Thus, neither { i }iI or { i }iI C are complete in R m .
In R m the phase of a vector can be equal to 0 or . Coordinates of the vectors have the same phases if signs of the coordinates of the vector x are the same as those of the vector y . At the same time the phase of 0 is not defined. That is, if x (a1 , a2 ,..., am ) and y (b1 , b2 ,..., bm ) , then x, y have the same phase in the following cases: 1) If ai 0 bi , then ai bi 0 . 2) If ai 0 , then corresponding to it bi 0 (it is symmetric: if bi 0 , then corresponding to it ai 0 ). Otherwise, the vectors have different phases.
Then, if we are given two vectors, so as to define whether their phases are equal or not it is necessary: 1) To check equality of all indices of zero coordinates of the vectors. If all indexes of zero coordinates of the first vector correspond to the indexes of the second vector (and vice versa), then it is necessary to check 2), otherwise, the vectors have different phases.
2) For nonzero coordinates to check fulfillment of the following condition: if ai bi 0 the vectors have the same phases, and if ai bi 0 then the vectors have different phases.
Definition 1 in the real case will mean: Let i i1 be a set of vectors in R m , satisfying the following property: for every x, y the following condition is n fulfilled:
x, i y, i , i 1,2,..., n . Then, 1) i i1 does phases reconstruction if there exist 1 such that
n а) For 1 the vectors x and y have the same phase.
b) For 1 the vectors x and y have the same phase. 2) i i1 does phaseless reconstruction if there exists 1 such that
n с) For 1 x y .
d) For 1 x y .
Theorem 2. Let i i1 be a set of vectors in R m . The mapping A : R m /{1} R n (n m) is defined by n equations ( A(x))(i) : x, i 2 , i 1,.., n . If i i1 does phase retrieval, then it has the complement property. In the real
n case these concepts are equivalent.
Proof. Assume that does phase retrieval, but fails phaseless reconstruction. Assume that the set i in1 fails complement property, that is there exists I {1,.., n} such that neither { i }iI , nor { i }iI C is complete in R m .
Let us choose nonzero vectors x (a1 , a2 ,..., am ), y (b1 , b2 ,..., bm ) R m such that x, i 0 for all i I and y, i 0 for all i I C . Then for some i either x, i 0 , or y, i 0 . Fix c 0 , so that for every 1 i n
By assumption, does phase retrieval, and it means that there exists 1 such that ( x cy) and ( x cy) have the But it is impossible because if x and y have the same phases, then ai 0 if and only if bi 0 .
As the vectors x and y are nonzero, then the last two equalities are possible if and only if either ai 0 , or bi 0 , 1 i m . Let I {1 i m : bi 0} and {ei }im1 be an orthonormalized basis in R m . Then x y ai ei bi ei and x y ai ei (bi )ei .
iI iI C iI iI C
Then there exists 1 such that ( x y) and ( x y ) have the same phases and they are equal. We have arrived at a contradiction.
Let's consider an example in R 2 . Let x (a1 , a2 ) (0,0) and y (b1 , b2 ) (0,0) .
For i i31 , we take the Mercedes-Benz frame in R 2 , consisting of 3 unit vectors located at an angle of 120º (Fig. 2): 1 (0,1), 2 ( 3 2
1 , ), 3 ( 2
x, i
Mathematical Modeling / А.А. Kuleshova, E.A. Shchelokov
y, i i31 means that (a1 , a2 ), ( (a1 , a2 ), ( (a1 , a2 ), (0,1) (b1 , b2 ), (0,1) 3 1
, 2 2 3 1
, ) 2 2 (b1 , b2 ), ( 3 1
, 2 2
) 3 1
, ) 2 2 ) (b1 , b2 ), ( a2 b2 3a1 a2 3b1 b2 . 3a1 a2 3b1 b2 Squaring the equations of the last system we obtain that
a1a2 b1b2 and a12 b12 .
From this it follows that the first equality gives coincidence of the signs (to the multiplier), and the second – coincidence of the absolute values of coordinates. Moreover, from these equalities it also follows that zero coordinates are the same, if any.
We obtain that either x y , or x y . Then there really exists 1 such that if i i1 is the Mercedes-Benz 3 frame, it does both phases reconstruction (because the vectors have the same signs, which means that the phases are the same too) and phaseless reconstruction (for x y ) at the same time.
If we know the absolute values of coordinates of the vectors x (a1 , a2 ) and y (b1 , b2 ) , then x and y can be one of 4 vectors (Fig. 3):
a2 b2 1 2 b1b2 a a a1
Mathematical Modeling / А.А. Kuleshova, E.A. Shchelokov Then fulfillment of the condition x, i y, i i51 means that ( x1 , x2 ), (1,0) ( y1 , y2 ), (1,0) ( x1 , x2 ), ( 12 , 12 ) ( y1 , y2 ), ( 12 , 12 ) ( x1 , x2 ), ( 12 , 12 ) ( y1 , y2 ), ( 12 , 12 ) ( x1 , x2 ), ( 12 , 12 i) ( y1 , y2 ), ( 12 , 12 i) ( x1 , x2 ), ( 1 , 1 i) ( y1 , y2 ), ( 1 , 1 i) 2 2 2 2
Then x, i (x1 , x2 ), ( i1 , i2 ) x j ij and x, i y, i i51 mean that: j1,2 i1,5 x1 xx21 xy11 x2 x1 x2 x1 x2 x1 x2 i x1 x2 i x1 x2 i x1 x2 i Let's rewrite the system in the following form: a 2 b 2 e 2 f 2 (a c) 2 (b d ) 2 (e g ) 2 ( f h) 2 (a c) 2 (b d ) 2 (e g ) 2 ( f h) 2 . (a d ) 2 (b c) 2 (e h) 2 ( f g ) 2 (a d ) 2 (b c) 2 (e h) 2 ( f g ) 2 .
c 2 d 2 g 2 h 2 .
And it means that the absolute values of the second complex coordinates of the vectors x and y are equal, because: c 2 d 2 x2 = g 2 h 2 y2 .
So, if we take a frame of the type 1 (1,0), 2 ( 12 , 12 ), 3 ( 12 , 12 ), 4 ( 12 , 12 i), 5 ( 12 , 12 i) , then the absolute values of the corresponding complex coordinates of the vectors x and y are equal, i.e.: x1 y1 r1 and x2 y2 r2 .
Now, let us write down the coordinates of the vectors in the polar form, taking into account the equality of the absolute values of the coordinates:
x (x1 , x2 ) (r1ei1 , r2ei2 ) and y ( y1 , y2 ) (r1ei 1 , r2ei 2 )) .
Then x, i y, i i51 will look as follows: (r1e i1 , r2 e i2 ), (1,0) (r1e i 1 , r2 e i 2 ), (1,0) (r1e i1 , r2 e i2 ), ( 12 , 12 ) (r1e i 1 , r2 e i 2 ), ( 12 , 12 ) (r1e i1 , r2 e i2 ), ( 12 , 12 ) (r1e i 1 , r2 e i 2 ), ( 12 , 12 ) (r1e i1 , r2 e i2 ), ( 12 , 12 i) (r1e i 1 , r2 e i 2 ), ( 12 , 12 i) (r1e i1 , r2 e i 2 ), ( 1 , 1 i) (r1e i 1 , r2 e i 2 ), ( 1 , 1 i) 2 2 2 2 .
From this it follows that 1 1 and 2 2 . We obtain that phases of the vectors x and y are equal to 2k, k .
Definition 1. Two vectors x (a1 , a2 ,..., am ) and y (b1 , b2 ,..., bm ) do weak phase retrieval if there is a 1 such that phase ai phase bi , for all i 1,2,..., m , such that ai 0 bi .
In the real case, if 1, we say that x, y have weakly like signs and if 1 they have weakly opposite signs. Definition 2. A family of vectors i i1 in m does weak phase retrieval if from equalities n
x, i y, i , i 1,2,..., n .
phase xi phase yi , for all i 1,2,..., m , so that ai 0 bi .
The weak phase retrieval differs from the phase retrieval described in Definition 2 of Section 4 in that there can be both ai 0 and bi 0 .
Let us consider an example where the weak phase retrieval is done but the phase retrieval by Definition 2 of Section 4 is failed. Let us consider in R m a set of vectors i im11 , which coordinates form the following matrix columns: 1 1 A 1 Then for every x (a1 , a2 ,..., am ) and y (b1 , b2 ,..., bm ) , if x, i y, i
i j bi b j for all i j . , it follows that a a This set of (m 1) -vectors in Rm will do weak phase retrieval.
Theorem 1: Let x (a1 , a2 ,..., am ) and y (b1 , b2 ,..., bm ) be two vectors in R m . Then the following statements are equivalent: 1) sgn(ai a j ) sgn(bi b j ) , for all 1 i j m .
2) x, y have either weakly like signs or weakly opposite signs.
In case the phase information is not available, the signal recovery is theoretically possible if redundant systems called frames are used as the system of representation. A well-chosen frame can provide numerical stability for recovery of the signal and obtaining important characteristics of the signal.
In the real case under certain conditions a generic frame consisting of (2m-1)-vectors can do phaseless reconstruction. In the complex space a generic frame consisting of (4m-2)-vectors can do the same under certain conditions. A family of frames recovers the signal by the absolute value of frame coefficients in polynomial time. The issue of the equivalence of phases retrieval and phaseless reconstruction is raised and partially resolved. Examples of signal recovery in small-dimension spaces are given.
A search and theoretical justification of new methods of recovery of information hidden in phases of transmitted signals and unavailable for measurements by publicly available physical instruments is conducted. The technique is based on the latest achievements in the research of complete linearly dependent systems called space frames.
Acknowledgements
The authors thank S.Ya. Novikov for his fruitful discussions.
Mathematical Modeling / А.А. Kuleshova, E.A. Shchelokov [10] Cahill J, Mixon DG. Full Spark Frames. Available online: arXiv:1110.3548. [11] Kuleshova A. Generic frame in problems for signal reconstruction without phase. Information Technology and Nanotechnology 2016, Ceur WS 2016.; 1638; 364–372.