=Paper=
{{Paper
|id=Vol-1638/Paper44
|storemode=property
|title=Generic frame in problems for signal reconstruction without phase
|pdfUrl=https://ceur-ws.org/Vol-1638/Paper44.pdf
|volume=Vol-1638
|authors=Antonina A. Kuleshova
}}
==Generic frame in problems for signal reconstruction without phase ==
https://ceur-ws.org/Vol-1638/Paper44.pdf
Image Processing, Geoinformatics and Information Security
GENERIC FRAME IN PROBLEMS FOR SIGNAL
RECONSTRUCTION WITHOUT PHASE
A.A. Kuleshova
Samara National Research University, Samara, Russia
Abstract. Search fast algorithms for signal reconstruction without phases rele-
vant now. Algorithms recovery are important in the treatment of a variety of
signals. Main frames property that makes them so useful in applications - re-
dundancy. Well selected frame can provide numerical stability for signal resto-
ration and getting the important characteristics of the signal.
Keywords: frame, reconstruction without phase, uniform frames
Citation: Kuleshova AA. Generic frame in problems for signal reconstruction
without phase. CEUR Workshop Proceedings, 2016; 1638: 364-372. DOI:
10.18287/1613-0073-2016-1638-364-372
Introduction
Search of algorithms for doing signal reconstruction without phase is the actual task.
Now the large number of articles on search of algorithms of the solution of this task is
let out. Recently the theoretical possibility of the solution of this task was shown [4].
It is shown that the family of frames recovers the signal on absolute value of frame
coefficients in polynomial time [1].
Another line of research is to find the minimum amount needed to restore the projec-
tions or vectors of information. For analytical, algebraic and probabilistic methods
will be attracted to this search. Increasing the growth rate transmit and process digital
information to explain the relevance of the proposed topic.
A search and theoretical basis of new methods of data recovery, hidden in the phases
of the transmitted signals, and is not available for measuring physical devices availa-
ble to the public. The methodology are the latest advances in the study of complete
linearly dependent systems called frames spaces.
Injective and the stability of mapping "measuring amplitude"
signal
Sampling and quantization of the analog signal lead to consideration of the signal as
element of some finite-dimensional space. In such space, generally speaking, complex,
Information Technology and Nanotechnology (ITNT-2016) 364
Computer Optics and Nanophotonics Kuleshova A.A. General frames in problems …
the complex scalar product and the corresponding Hermite norm is entered. On or-
N
thonormalized basis (ONB) {ui }i 1 "signal" uniquely is represented the sum
N
v v, u i u i
i 1
Complex coefficients of the described representation v, ui give the possibility of the
complete signal reconstruction and often are understood as "measurements" of the
signal. Real measurements turn out real, both the gap between v, ui and amplitudes
of measurements v, ui is insuperable at signal reconstruction.
Representing the signal in different bases, it is possible to obtain about it various in-
formation. So, transition from representation on basis vectors to representation in Fou-
rier's basis, allows to receive the frequency characteristics of the signal giving ample
opportunities for its digital processing.
The last years the significant amount of works is devoted to the decision the following
task: to construct such systems of "measuring" vectors F f i iM1 , which allow to
recover the arbitrary signal v V on the set of real numbers v, f i .
In class ONB such task has no decision.
The main problem delivered in [13] is still far from the final decision:
To find necessary and sufficient conditions on system of vectors of representation
F f i iM1 (so-called "measuring vectors") which provide the injective and stability
of mapping of "measurement of amplitude" of the signal x
2
( A( x))( i ) : x, f i
Definition range of this mapping is the space V = R N or C N . Let's notice, however,
that (x) = (y) if y = cx for some scalar c with the unit module. Therefore, strictly
speaking, mapping : V R M cannot be injective.
1
Therefore we will consider as definition range or R N /{±1} , or C N /T1 , where T
- the complex unit circle on the complex plane. At such agreement questions about
injectives and stability of mapping are informative.
To reconstruction the signal x it is impossible if mapping is not injective.
Definition 1. A set of vectors F f i iM1 in R N (or C N ) yields phase retrieval if
M M
for all x, y R N (or C N ) satisfying x, f i y, f i then y = cx , where
i 1 i 1
c 1 in R N and c T1 in C N .
Definition 2. Let F f i iM1 be a family of vectors in R N (or C N ) satisfying: for
M M
every x and y in R N (or C N ) execute equalities: x, f i y, f i
i 1 i 1
1) If this implies there is a with | |=1 so that x and y have the same phases,
we say F f i iM1 does phase retrieval;
Information Technology and Nanotechnology (ITNT-2016) 365
Image Processing, Geoinformatics and Information Security Kuleshova AA…
2) If this implies there is a with | |=1 so that x y , we say F f i iM1 does
phaseless reconstruction.
Frames
Definition 1. A family of vectors f i iM 1 is a frame for a Hilbert space HN if there
M 2
are such constants 0 < A ≤ B < ∞, if for all x ∈ H: A || x || 2 x, f i B || x || 2 .
i 1
A and B are called frame borders. The greatest of the lower bounds is called the opti-
mum lower bound, and the smallest of the upper bounds - the optimum upper bound.
If A=B this is a A-tight frame and if A=B=1, it is called a Parseval frame.
The numbers x, f i iM1 are called the frame coefficients.
If all the frame elements have the same norm we call this an uniform frame.
In finite-dimensional space the concept of the frame is equivalent to concept of com-
pleteness of system, i.e. equality span{ f i }iM1 R N ( span{ f i }iM1 C N ).
Definition 2: Let f i iM1 - the frame, linear mapping:
T : H N H M l 2 ( I ), T ( x ) x, f i i 1
M
is called the analysis operator.
Definition 3. Linear mapping:
M
T * : H M l 2 ( I ) H N , T * (ci iM1 ) ci f i
i 1
is called the synthesis operator.
*
The composition T and T defines the frame operator – the positive, self-conjugate
reversible operator:
M
S T *T : H N H N : Sx T *Tx x, f i f i
i 1
It provides the exact formula for reconstruction:
M
x x, f i S 1 f i .
i 1
Definition 4. A family of vectors F f i iM1 is said uniform equiangular tight frame
if
______
1) 0 : || f i || i 1, M ;
2) c 0 : such that for all pairs of frame vectors f j and f k , j≠k, we have:
f j , f k c.
Information Technology and Nanotechnology (ITNT-2016) 366
Computer Optics and Nanophotonics Kuleshova A.A. General frames in problems …
It is known that there is the upper bound for number of vectors in the uniform equian-
gular tight frame F f i iM1 on the N-dimensional Hilbert space of H. In the real
N ( N 1)
case it M , in the complex case - M N 2 ([10], [3]). Creation of the
2
maximum number of vectors for the uniform equiangular tight frame very complex
and unresolved challenge in the theory of frames.
Generic frame
In work [1] is shown that a generic frame will give signal reconstruction without
phase and will achieve this in polynomial time.
We consider the non-linear mapping taking a vector to the absolute value of its
frame coefficients:
M
: H l 2 ( I ), ( x ) x, f i .
i 1
If it is necessary to associate to its frame F f i iM1 we will write F .
Let H r H / ~ be the quotient space obtained by identifying two vectors if they
differ by a constant phase factor. That is, x~y means there is a scalar c:|c|=1 so that
y=cx.
For real Hilbert spaces, с 1 , then H r H /{1} .
For complex Hilbert spaces c e i , then H r H /{T } - the complex unit circle on
1
the complex plane. In quantum mechanics, these projective rays define quantum states
[12].
The nonlinear mapping extends to H r as
M
: H r N H M l 2 ( I ), ( xˆ ) x, f i , x xˆ.
i 1
If H R the set I consists of М-elements, I {1,..., M } . Then l ( I ) R
N 2 M
.
M
The set Gr ( N , M ; R ) of N-dimensional linear subspaces of R has the structure of
an N(M−N)-dimensional manifold.
The set Gr ( N , M ; R ) called the Grassmann manifold.
For a frame F f i iM1 of R N the analysis operator satisfies:
M
T : R N R M , T ( x ) x, f i ei ,
i 1
where {e1 ,..., e M } is the canonical basis of R M .
The considered nonlinear mapping in the real case:
Information Technology and Nanotechnology (ITNT-2016) 367
Image Processing, Geoinformatics and Information Security Kuleshova AA…
M
F : R N /{1} R M , F ( xˆ ) x, f i ei , x xˆ.
i 1
Two frames and are equivalent if there is an invertible operator O on H with
O ( f i ) g i , for all I {1,..., M } . It is known that two frames are equivalent if and
only if their associated analysis operators have the same range [2, 9].
In [4] it is shown that two equivalent frames F and G have the property that F is
injective if and only if G is injective.
If H C N then for an M-element frame F f i iM1 the analysis operator is defined
also, as well as for the real case:
M
T : R N R M , T ( x ) x , f i ek .
k 1
N ___
The scalar product by definition: x, y x k y k .
k 1
The nonlinear map:
M
F : R N /{T 1 } C M , F ( xˆ ) x, f k ek , x xˆ ,
k 1
where two vectors x , y xˆ if there is a scalar c C : c 1 so that y cx .
Definition 1. The frame is called generic frames if f i i 1 L U , where U - Zar-
M
iski open set and U Gr ( N , M ) .
The main results from [4]:
Theorem 1. (The real case) [13] If M 2N 1 , then for a generic frames
F f i iM1 nonlinear mapping is injective.
Proof. Suppose that x and x have the same image under . Let a1 ,..., a M be the
frame coefficients of x and a 1 ,..., a M the frame coefficients for x . Then a i a i
for each i .
(i )
In particular there is a subset {1,..., M } of indices such that ai ( 1) ai .
Then two vectors x and x have the same image under if and only there is a
(1)
subset {1,..., M } such that a1 ,..., a M and ( 1) a1 ,..., ( 1) ( M ) a M are both
in W the range of coefficients associated to F.
To finish the proof we will show that when M 2N 1 such a condition is impossi-
ble for a generic subspace W R .
N
This means that the set of such W ’s is a dense (Zariski) open set in the Grassmanian
Gr(N,M). In particular the probability that a randomly chosen W will satisfy this
condition is 0.
To finish the proof of the theorem we need the following lemma.
Lemma 1. If M 2N 1 then the following holds for a generic N-dimensional sub-
space W R . Given u W , then (u ) W iff (u ) u .
N
Information Technology and Nanotechnology (ITNT-2016) 368
Computer Optics and Nanophotonics Kuleshova A.A. General frames in problems …
Proof. Suppose u W and (u ) u , but (u ) W .
Since is an involution, (u (u )) is fixed by and is nonzero. Thus
W L 0 .
Likewise 0 u (u ) u C (u ).
Hence, W L 0 .
C
Now L and L are fixed linear subspaces of dimension M and . If
C
M 2N 1 then one of these subspaces has codimension greater than or equal to N.
However a generic linear subspace W of dimension N has 0 intersection with a fixed
linear subspace of codimension greater than or equal to N.
Therefore, if W is generic and x , ( x) W , then ( x) x which ends the
proof of lemma.
The proof of the theorem now follows from the fact that if W is in the intersection of
generic conditions imposed by the proposition for each subset {1,.., M } then W
satisfies the conclusion of the theorem.
Definition 2. The family of vectors f i i1 R N is called the set with the full spark,
M
if every subset from N vectors is full in R N .
For the analysis injectives complement property is important.
Definition 3. We say F f i iM1 in R N ( C ) satisfies the complement property if
N
for all subsets {1, . . . , M} , either { f i }i or { f i }i C full in R N ( C ) .
N
Theorem 2. Consider F f i iM1 - set of vectors in R N . The mapping
2
A : RrN R N /{1} R M defined by ( A( x))(i ) : x, f i , i 1,.., M .
Then A is injective if and only if then F satisfies the complement property.
Proof. ( ) Assume that F is not complement property. Then there exists
{1,.., M } such that neither f i i nor f i i C not full in R N .
This implies that there are nonzero vectors u, v R N such that u , f i 0 for all
i and v, f i 0 for all i C .
For each i we then have
________
2 2 2 2 2
u v, f i u, f i 2 u, f i v, f i v, f i u, f i v, f i
2 2
From this it follows that u v, f i u v, f i for every i , we have
A(u v ) A(u v ) . Moreover, u and v are nonzero by assumption, and so
u v (u v ) .
() Assume that A is not injective. Then there exist vectors x, y R N such that
x y and A( x ) A( y ) . Taking : {i : x, f i y , f i } .
Information Technology and Nanotechnology (ITNT-2016) 369
Image Processing, Geoinformatics and Information Security Kuleshova AA…
We have x y , f i 0 for every i . Otherwise when i C , we have
x, f i y , f i and so x y , f i 0 . According to the assumption, x y there-
fore x y 0 and x y 0 .
Thus, { f i }i and { f i }i C , are not full in R N .
Theorem 3 [13]. Consider F f i iM1 C N and the mapping
2
A : C rN C N / T 1 R M defined by ( A( x))(i ) : x, f i , i 1,.., M .
Viewing { f i f i*u}iM1 as vectors in R 2 N , denote S (u ) : spanR { f i f i*u}iM1 . Then the
following are equivalent:
(a) A is injective.
(b) dim S (u ) 2 M 1 for every u C N \ {0} .
(c) S (u ) spanR {iu} for every u C N \ {0} .
Lemma 2. Everyone set with the full spark F f i iM1 in R N with M 2N 1
satisfies to complement property.
Proof. Let's assume opposite: exists {1,.., M } such that neither f i i nor
f i i not full in R N .
C
By definition of the full spark, from this it follows that N 1 and C N 1 ,
that is M 2 N 2 that contradicts the condition.
Theorem 4. In the real case if F f i iM1 in R N and M 2 N 2 , then mapping is
not injective.
If M 2N 1 , then mapping A is injective if and only if then F f i iM1 - full
spark.
Proof. If M 2 N 2 , then the set {1,.., M } can be broken into sets and
C
so
that the cardinality of everyone sets did not exceed N 1 . Any of sets { f i }i ,
{ f i }i C cannot be full.
If M 2N 1 and F f i iM1 - full spark, then the injective A follows from the
lemma 2 and theorems 3.
Back, if A - injective, then F f i iM1 satisfies to complement property. Let's take
any subset {1,.., M } with N . Then C N 1 and { f i }i C can’t be full.
Therefore, { f i }i - full, and F f i iM1 - full spark.
We do not know the exact minimal bound for the complex case. Also, in the real case
there is a simple direct method for checking if A is injective for a given frame [4].
Information Technology and Nanotechnology (ITNT-2016) 370
Computer Optics and Nanophotonics Kuleshova A.A. General frames in problems …
Consequence 1. If F is a M-element frame for R N with M 2N 1 having the
property that every N-element subset of the frame is linearly independent, then
A : H N r H M l 2 ( I ) is injective.
Theorem 5. (Complex frames) If M 4 N 2 then for a generic frame F, the nonlin-
ear map A is injective.
The (4M − 4) Conjecture. Consider F f i iM1 C N and the mapping
2
A : CrN C N /{T 1 } R M defined by ( A( x))(i ) : x, f i , i 1,.., M . If M 2 ,
then the following statements hold:
(a) If M 4 N 4 , then A is not injective.
(b) If M 4 N 4 , then A is injective for some frames.
In work [1] is shown that a generic frame will give signal reconstruction without
phase in a polynomial number.
Let H be a fixed N-dimensional vector space which is assumed to be either real or
complex and let {e1 ,.., e N } be a chosen orthonormal basis for H. We will henceforth
refer to this as the “standard basis” for H.
Theorem 6 [1].
N ( N 1)
(a) If H R N , M and F f i iM1 is a generic frame, nonlinear map P
2
is injective. Then vector x H can be reconstructed (up to sign) from the set
{| x, f i |} iM1 of modules of the frame coefficients in a polynomial number
(O(N 6 )) of steps.
(b) If H C N , M N 2 and F f i iM1 is a generic, nonlinear map P is injective.
Then vector x H can be reconstructed (up to multiplication by a root of unity) from
the set {| x, f i |} iM1 of modules of the frame coefficients in a polynomial number
(O(N 6 )) of steps.
Conclusion
Recovery of the signal is possible in case of lack of phase information which is lost
during processing of the signal. Examples of such signals without phase are processes
of transfer and processing of images. Recovery of the lost information is necessary for
the subsequent work with data. At loss of part of information the above described
mathematical methods and estimates give information that it is possible to recover the
signal on modules of frame coefficients for polynomial number of steps
Further detailing is necessary for frames of the general provision.
Information Technology and Nanotechnology (ITNT-2016) 371
Image Processing, Geoinformatics and Information Security Kuleshova AA…
Acknowledgements
I would like to express my gratitude and appreciation to my supervisor, Professor,
Doctor of Physical and Mathematical Sciences Novikov Sergey Yakovlevich for par-
ticipation in the discus-sion of the results and help in preparing this article.
References
1. Balan RB, Bodmann G, Casazza PG, Edidin D. Fast algorithems for signal reconstruction
without phase. Proceedings of SPIE-Wavelets XII, San Diego, 2007; 6701: 670111920-
670111932.
2. Balan R. Equivalence relations and distances between Hilbert frames. Proc. Amer. Math.
Soc., 1999; 127(8): 2353-2366.
3. Balan R, Bodman BG, Casazza PG and Edidin D. Painless reconstruction from magnitudes
of frame coefficients, preprint.
4. Balan R, Casazza P, Edidin D. On signal reconstruction without phase. Appl. Comput.
Harmon. Anal., 2006; 20: 345-356.
5. Calderbank AR, Cameron PJ, Kantor WM, Seidel JJ. Z4-Kerdock codes, orthogonal
spreads, and extremal Euclidean line-sets. Proc. London Math. Soc., 1997; 75(3), N 2:
P. 436-480.
6. Cameron PJ, Seidel JJ. Quadratic forms over GF (2). Indag. Math., 1973; 35:1-8.
7. Casazza PG, Fickus M. Fourier transforms of finite chirps. EURASIP J. Appl. Signal Pro-
cess, Frames and overcomplete representations in signal processing, communications, and
information theory, Art. ID 70204, 2006: 1-7.
8. Delsarte P, Goethals JM, Seidel JJ. Spherical codes and designs, Geometriae Dedicata,
1977; 6(3): 363-388.
9. Han D, Larson D. Frames, bases and group representations. Memoirs American Math.
Soc., 2000 ; 147, N 697.
10. Holmes R, Paulsen VI. Optimal frames for erasures. Lin. Alg. Appl., 2004; 377: 31-51.
11. Howard SD, Calderbank AR, Moran W. The finite Heisenberg-Weyl groups in radar and
communications. EURASIP J. Appl. Signal Process, no. Frames and overcomplete repre-
sentations in signal processing, communications, and information theory, Art. ID 85685,
2006: 1-12.
12. Streater RF, Wightman AS. PCT, Spin and Statistics and All That. Princeton University
Press, Landmarks in Mathematics and Physics, 2000.
13. Bandeira A, Cahill J, Mixon D, Nelson A. Saving phase: Injectivity and stability for phase
retrieval. Applied and Computational Harmonic Analysis (ACHA), 2014; 37(1): 106-125.
Information Technology and Nanotechnology (ITNT-2016) 372