Search fast algorithms for signal reconstruction without phases relevant now. Algorithms recovery are important in the treatment of a variety of signals. Main frames property that makes them so useful in applications - redundancy. Well selected frame can provide numerical stability for signal restoration and getting the important characteristics of the signal. 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,
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 [
Another line of research is to find the minimum amount needed to restore the projections 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 available to the public. The methodology are the latest advances in the study of complete linearly dependent systems called frames spaces. the complex scalar product and the corresponding Hermite norm is entered. On or
N thonormalized basis (ONB) {ui }i1 "signal" uniquely is represented the sum
N v v, ui i1
ui 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 information. So, transition from representation on basis vectors to representation in Fourier'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 fi iM1 , which allow to recover the arbitrary signal v V on the set of real numbers v, fi .
The main problem delivered in [
2 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.
Therefore we will consider as definition range or R N /{±1} , or C N /T1 , where T1 - 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 fi iM1 in R N (or C N ) yields phase retrieval if M x, fi i1
M y, fi i1 then y = cx , where for all x, y R N (or C N ) satisfying c 1 in R N and c T1 in C N .
Definition 2. Let F fi iM1 be a family of vectors in R N (or C N ) satisfying: for every x and y in R N (or C N ) execute equalities:
M x, fi i1
M y, fi i1 1) If this implies there is a with | |=1 so that x and y have the same phases, we say F fi iM1 does phase retrieval; 2) If this implies there is a with | |=1 so that x y , we say F f i iM1 does phaseless reconstruction.
Definition 1. A family of vectors f i iM 1 is a frame for a Hilbert space HN if there M are such constants 0 < A ≤ B < ∞, if for all x ∈ H: A || x || 2 x, f i B || x || 2 . i1 A and B are called frame borders. The greatest of the lower bounds is called the optimum 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 i1 are called the frame coefficients.
M 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 completeness of system, i.e. equality span{ f i }i1 R N (span{ f i }i1 C N ).
M M 2 Definition 2: Let f i iM1 - the frame, linear mapping: T : H N H M l 2 ( I ), T ( x) x, f i i1
M is called the analysis operator.
Definition 3. Linear mapping: T * : H M l 2 (I ) H N , T * (ci iM1 ) M ci f i
i1 if 1) 2) f j , f k
c. 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
i1 It provides the exact formula for reconstruction:
M x x, f i S 1 f i .
i1 Definition 4. A family of vectors F f i iM1 is said uniform equiangular tight frame 0 : || f i ||
______ i 1, M ; c 0 : such that for all pairs of frame vectors f j and f k , j≠k, we have: It is known that there is the upper bound for number of vectors in the uniform equiangular tight frame F fi 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 ([
In work [
We consider the non-linear mapping taking a vector to the absolute value of its frame coefficients:
: H l 2 (I ), ( x) x, fi M .
i1 If it is necessary to associate to its frame F fi 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 ei , then H r H /{T 1} - the complex unit circle on
the complex plane. In quantum mechanics, these projective rays define quantum states
[
The nonlinear mapping extends to H r as
: H r N H M l 2 (I ), ( xˆ) x, fi M , x xˆ. i1 If H R N the set I consists of М-elements, I {1,..., M } . Then l 2 (I ) R M . The set Gr ( N , M ; R) of N-dimensional linear subspaces of R M has the structure of an N(M−N)-dimensional manifold.
The set Gr ( N , M ; R) called the Grassmann manifold.
For a frame F fi iM1 of R N the analysis operator satisfies:
M T : R N R M ,T (x) x, fi ei ,
i1 where {e1 ,..., eM } is the canonical basis of R M .
The considered nonlinear mapping in the real case: injective if and only if G is injective.
If H C N then for an M-element frame F fi iM1 also, as well as for the real case:
M T : R N R M ,T (x) x, fi ek .
k1
N ___ The scalar product by definition: x, y xk yk .
k1
M F : R N /{1} R M , F (xˆ) x, fi ei , x xˆ.
i1
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 [
In [
M F : R N /{T 1} C M , F (xˆ) x, fk ek , x xˆ,
k1 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 fi iM1 L U , where U - Zariski open set and U Gr ( N , M ) .
Theorem 1. (The real case) [
Proof. Suppose that x and x have the same image under . Let a1 ,..., a M be the frame coefficients of x and a1 ,..., a M the frame coefficients for x . Then ai ai for each i .
In particular there is a subset {1,..., M } of indices such that ai (1) (i) ai . Then two vectors x and x have the same image under if and only there is a subset {1,..., M } such that a1 ,..., a M and (1) (1) a1 ,..., (1) (M ) aM 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 impossible 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 subspace W R N . Given u W , then (u) W iff (u) u . 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 C 0 .
Now L and L C are fixed linear subspaces of dimension M and . If 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 fi iM1 R N is called the set with the full spark, if every subset from N vectors is full in R N .
For the analysis injectives complement property is important.
Definition 3. We say F fi iM1 in R N ( C N ) satisfies the complement property if for all subsets {1, ... , M}, either { fi }i or { f i }i C full in R N ( C N ) . Theorem 2. Consider F fi iM1 - set of vectors in R N . The mapping A : RrN R N /{1} R M defined by ( A(x))(i) : x, fi 2 , 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 u v, fi u, fi 2
2 u, fi From this it follows that ________ v, fi v, fi 2 u, fi 2 v, fi
2 2 u v, fi u v, fi 2 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 } .
x y, f i 0 for every i . Otherwise when i C , we have x, fi y, fi and so x y, fi 0 . According to the assumption, x y therefore x y 0 and x y 0 .
Thus, { fi }i and { f i }i C , are not full in R N .
Theorem
3
[
F f i iM1 C N and the mapping A : CrN C N / T 1 R M defined by ( A(x))(i) : x, fi 2 , i 1,.., M .
Viewing { fi fi*u}iM1 as vectors in R2N , denote S (u) : spanR { f i f i*u}iM1 . Then the following are equivalent: (a) A is injective. (b) dim S (u) 2M 1 for every u C N \ {0} . (c) S (u) spanR {iu} for every u C N \ {0} . satisfies to complement property.
Proof. Let's assume opposite: exists {1,.., M } fi i C not full in R N .
Lemma 2. Everyone set with the full spark F fi iM1 in R N with M 2N 1 such that neither fi i nor not injective. spark.
By definition of the full spark, from this it follows that N 1 and C N 1 , that is M 2N 2 that contradicts the condition.
Theorem 4. In the real case if F fi iM1 in R N and M 2N 2 , then mapping is If M 2N 1 , then mapping A is injective if and only if then F fi iM1 - full Proof. If M 2N 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 { fi }i , { f i }i C cannot be full. lemma 2 and theorems 3.
If M 2N 1 and F fi iM1 - full spark, then the injective A follows from the Back, if A - injective, then F fi 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, { fi }i - full, and F fi 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 [
Theorem 5. (Complex frames) If M 4N 2 then for a generic frame F, the nonlinear map A is injective.
The (4M − 4) Conjecture. Consider F fi iM1 C N and the mapping A : CrN C N /{T 1} R M defined by ( A(x))(i) : x, fi 2 , i 1,.., M . If M 2 , then the following statements hold: (a) If M 4N 4 , then A is not injective. (b) If M 4N 4 , then A is injective for some frames.
In work [
Let H be a fixed N-dimensional vector space which is assumed to be either real or complex and let {e1 ,.., eN } be a chosen orthonormal basis for H. We will henceforth refer to this as the “standard basis” for H.
Theorem 6 [
N ( N 1) (a) If H R N , M and F fi 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 fi 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.
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.
I would like to express my gratitude and appreciation to my supervisor, Professor, Doctor of Physical and Mathematical Sciences Novikov Sergey Yakovlevich for participation in the discus-sion of the results and help in preparing this article.