Frames and subspaces, that are used to the reconstruction of the vector signal without phase measurements, represented. The new concept of equidistributed frames is considered. The possibility of reconstruction of the vector by the norms of the projections on the subspaces is asserted. Particular attention is paid to systems of subspaces for which there is the possibility of reconstruction by the norms of the projections on them and on their orthogonal complements. Let HM denotes M-dimensional space with the scalar product. Definition 1. A set of vectors Φ = {φ k}k=1 is called a frame for the HM , if there are positive constants A, B such N that for all x ∈ HM k=1 Numbers A and B are called the lower and upper frame bounds respectively. If we can choose A = B, then the frame is called tight, and if A = B = 1, it is called a Parseval-Steklov frame (This name was proposed by Acad. V.S. Vladimirov during a report of the second author in Math. Steklov Institute in 2008 instead of usual Parseval Frame). Note that in the finite dimensional setting, a frame is simply a spanning set of vectors in the Hilbert space (span{φ k}kN=1 = HM ) [1, 2]. There are three operators connected with a frame Φ: analysis operator T : HM → ℓ2N , defined by ⟨x, φ k⟩φ k.
N ∑ A x 2 ∥ ∥ ≤
|⟨x, φ k⟩|2 ≤ B∥x∥2. adjoint synthesis operator and frame operator S := T ∗T on HM , defined by
N
N ) = ∑ T ∗ ({ak}k=1
akφ k k=1
N S (x) = T ∗T (x) = ∑
AI ≤ S ≤ BI, Preprint submitted to Elsevier The operator G = T T ∗ is Gram operator with the matrix ⟨φ ∥φ1,...1φ∥22⟩ ⟨φ ∥2φ,...2φ ∥12⟩, ... ... ... ⟨⟨φφ NN ...,, φφ 12⟩⟩ ⟨φ 1, φ N ⟩ ⟨φ 2, φ N ⟩ . . . ∥φ N ∥2
N A∥x∥2 = A ∥Px∥2 ≤ ∑ |⟨Px, φ k⟩|2 =
N = ∑ |⟨x, P φ k⟩|2 ≤ B∥Px∥2 = B∥x∥2.
k=1 k=1 and for the Parseval-Steklov frame coincides with the projection P : ℓ2N → ℓ2N to the image of the analysis operator [1, 2].
An easy way is known to construct Parseval-Steklov frames. It is based on the following proposition. Proposition 1. Let {φ k}k=1 be a frame for HM with bounds A and B, and let P be the orthogonal projection in HM N
N N on the subspace W. Then {Pφ k}k=1 is a frame for W with bounds A and B. In particular, if {φ k}k=1 is Parseval-Steklov frame for HM and P is the orthogonal projection on W, then {Pφ k}k=1 is Parseval-Steklov frame for W. N
Corollary 1. Let {ek}k=1 be an orthonormal basis (ONB) in HM, and let P be the orthogonal projection on the
M
M subspace W. Then {Pek}k=1 is Parseval-Steklov frame for W.
Corollary 1 is the foundation of the following algorithm for construction of Parseval-Steklov frame. We construct N × N unitary matrix for N ≥ M, then we choose any M rows, columns of thus obtaining M × N-matrix form ParsevalSteklov frame in HM. If we construct from the remaining N − M rows (N − M) × N-matrix, then its columns are Parseval-Steklov frame in HN−M.
The following theorem, actually proved by Naimark, shows that such process is essentially the only one for constructing Parseval-Steklov frame [3].
Let Φ = {φ k}k=1 be a frame in HM with the analysis operator T, let {ek}k=1 be the standard basis in ℓ2N , let
N N
The following assertions are equivalent: 1. Φ is Parseval-Steklov frame for HM. 2. For all k = 1, . . . , N we have Pek = T φ k. 3. There are vectors {ψk}k=1 ⊂ HN−M such that {φ k ⊕ ψk}kN=1 form ONB in HN .
N Besides, {ψk}k=1 are Parseval-Steklov frame in HN−M.
N Proof.
N
(
(
⟨φ i ⊕ ψi, φ k ⊕ ψk⟩ = ⟨φ i, φ k⟩ + ⟨ψi, ψk⟩ = ＲＱＵ
= ⟨T φ i, T φ k⟩ + ⟨di, dk⟩ = δik.
(
N As in [4], we call vectors {ψk}k=1 Naimark complement of the frame Φ .
For Parseval-Steklov frame, written as {Pek}kN=1 , Naimark complement is the system of vectors {(I − P)ek}kN=1.
Naimark complements are defined only for Parseval-Steklov frames, and they are defined up to unitary equivalence. If {φ k}kN=1 ⊂ HM and {ψk}kN=1 ⊂ HN−M complement each other, U and V are unitary operators (U∗U = UU∗ = I) ,
N N then {Uφ k}k=1 , {Vψk}k=1 also complement each other.
An important application of frames is the reconstruction of a signal with incomplete data. In particular, much attention is attracted to the problem of the reconstruction phase information. In recent papers on this topic two aspects of the problem were emphasized: phaseless reconstruction and phase retrieval [7]. This paper focuses on the first aspect.
Definition 2. The set of vectors Φ = {φ i}iN=1 in RM (or CM) provides phaseless reconstruction (PLR), if equalities of measurement modules |⟨x, φ i⟩| = |⟨y, φ i⟩|,
x, y ∈ RM (CM), i = 1, . . . , N, imply the equality of vectors-signals up to unimodular factor, i.e. x = cy with some c = ±1 for RM or c ∈ T for CM, where T is the unit circle in C.
In the rest of the text sets, which are satisfied the definition of 2, is called PLR-systems or PLR-sets. The next property is important in these questions.
Definition 3 [4, 5]. The set Φ = {φ n}n=1 in HM has complement property (CP), if for any S ⊆ {1, . . . , N} {φ n}n∈S
N or {φ n}n∈S c is complete in HM. Complement property in RM is equivalent to PLR (theorem 2 below).
Definition 4 [4, 5, 6]. The spark of the set Φ = {φ n}n=1 ⊂ HM is the cardinality of the smallest linear dependent
N subset of Φ. If spark(Φ) = M + 1, then any subset with M vectors linear independent, in thus case Φ is called full spark set.
In earlier works the term ”girth” was used instead of the term ”spark”. Spark of the linear independent system, for example, basic, is assumed to be zero.
Theorem 2 [5, 8].
Frame {φ n}n=1 in RM is the PLR-system iff it has complement property. In particular, full spark frame with at least
N 2M − 1 vectors is PLR-system. If {φ n}n=1 is PLR-system in RM, then N ≥ 2M − 1, any subset with 2M − 2 vectors
N can’t be PLR-system.
Generally speaking, the recovery without phases is possible not only by full spark frames. Each frame, containing (2M − 1) full spark frame, will also provide recovery without phases. However, if the frame contains exactly 2M − 1 elements, it is a PLR-system only for full spark frame [5, 8.
If Φ is the Parseval-Steklov frame for HM with N elements, the analysis operator is isometric according to
N ∥T x∥2 = ∑ |⟨x, φ n⟩|2 = ∥x∥2 ,
x ∈ HM.
n=1
In this case, we obtain the reconstruction identity x = ∑nN=1 |⟨x, φ n⟩| φ n, or x = T ∗T x. In this case, we also have that the Gramian G := T T ∗ is a rank-M orthogonal projection, because G∗G = T T ∗T T ∗ = T T ∗ = G and the rank of G equals the trace, trG = M.
Definition 5. Two frames Φ = {φ n}n=1 and Φ′ = {φ ′n}nN=1 for a finite dimensional space HM are called unitarily
N equivalent if there exists an orthogonal or unitary operator U on HM such that φ n = Uφ ′n for n = 1, . . . , N.
Each equivalence class of frames is characterized by the corresponding Gram matrix.
Proposition 2 [13]. The Gramians of two frames Φ = {φ n}n=1 and Φ′ = {φ ′n}nN=1 for HM are identical if and only if N the frames are unitarily equivalent. ＲＱＶ In [13] the new class of frames is introduced.
Definition 6. Let Φ = {φ n}nN=1 be Parseval-Steklov frame for HM, let G be its Gramian. The frame Φ is called equidistributed if for each pair p, q ∈ ZN there exists a permutation π on ZN such that G j,p = Gπ( j),q for all j ∈ ZN .
In other words, Φ is equidistributed if and only if the magnitudes in any column of the Gram matrix repeat in any other column, up to a permutation of their position.
Proposition 3. If Φ = {φ n}nN=1 is an equidistributed Parseval-Steklov frame in HM, then ∥φ n∥2 = M/N, n = 1, 2, . . . , N.
Proof. By assumption, for each n there exists π such that Gn,p = Gπ(n),1 holds for the entries of the associated Gram matrix G for all n. By the Parseval-Steklov identity φ p 2 = ∑N n=1 ⟨φ p, φ n⟩ 2 = ∑N
Gn,p n=1 2 = ∑N n=1
Gπ(n),1 2 = ∥φ 1∥2 .
The trace condition ∑nN=1 Gn,n = ∑nN=1 φ p 2 = M for the Gram matrices of Parseval-Steklov frames implies that ∥φ n∥2 = M/N, n = 1, 2, . . . , N.
1. Equiangular Parseval-Steklov frames.
Let Φ = {φ n}nN=1 be an equal-norm frame and there exists C ≥ 0 such that ⟨φ n, φ ′n = C⟩ for all n, n′ ∈ ZN with n , n′. Such frames are called equiangular. Such Parseval-Steklov frames exist only with some restrictions on N and M [13]. The simplest example of the equiangular Parseval-Steklov frame in R2 is a well-known ”Mercedes-Benz frame”.
Magnitudes of the entries of any column of G for such frame consist of N − 1 instances of C and one instance of M/N, so Φ is equidistributed.
2. Mutually unbiased bases.
Such frame is union of orthonormal bases such that the modulus of the inner product between any two vectors from distinct bases is constant. Such examples are widely used in quantum information theory. The simplest example of mutually unbiased bases in C2 is given by the following three bases:
M0 =
(
1 (
1 (
To get the Parseval-Steklov frames one should renorm vectors to Φ because of these 3 matrices must the multiplied to 1/ √3. We get the Gram matrix 031 G = λλ λ λ 0 1 3 λ −λ iλ −iλ λ λ 1 3 0 1+i 16−i 6 λ −λ 0 1 13−i 6 1+i 6 λ −iλ 1−i 6 1+i 6 1 3 0 λ iλ 1+i 16 i , − 6 0
1 3 where λ = √2/6.
3. Group frames.
Let Γ be a finite group of size N = |Γ| and π : Γ → B (HM) be an orthogonal or unitary representation of Γ on the real or complex space HM respectively.
The orbit Φ = { fg = π(g) fe}g Γ , generated by a vector fe of norm √N/M, indexed by the unit e of the group, ∈ forms the Parseval-Steklov frame, if the representation is irreducible [14].In this case Φ is equidistributed, because ⟨ fg, fh⟩ = ⟨π (h−1g) fe, fe⟩ , and left multiplication hyh−1 acts as a permutation on the group elements. So the entries of Gram matrix has equal modules, up to a permutation in rows (columns).
4. Cycle frames. ＲＱＷ Consider the Discrete Fourier Transform matrix
F = √1N (ω jl)Nj,l=1 , where
2πi ω = e N .
Its columns form an orthonormal basis for CN . If A is a M × N matrix obtained by deleting any choice of N − M rows from F, then its columns form a Parseval-Steklov frame for CN .
Definition 7. Let b1, . . . , bM ∈ {1, 2, . . . , N} be any choice of distinct integers. F frame Φ = {φ n}n ∈ ZN , where φ n = √1N (ωnlm )mN=1 , f or all n ∈ ZN , is called a cycle frame.
Every cycle frame is equidistributed, and, because the construction described above works for every pair of positive integers M and N with M < N, the existence of equidistributed frames is ensured in the complex setting.
For every N > M there exists equidistributed Parseval-Steklov frame in CM with N vectors.
Let’s see if the possibility of recovery without phases is transferred to the Naimark complements. We require the following theorem for this.
Theorem 4 [9].
Let P be an projection in HN with ONB {en}n=1 and S ⊂ {1, 2, . . . , N}.
N The following assertions are equivalent: 1. {Pei}i∈S linear independent. 2. span {(I − P)ei}i∈S c = (I − P) (HN ) .
Proof.
(
span {(I − P)ei}i∈S c , (I − P) (HN ) . ⟨x, (I − P)ei⟩ = ⟨(I − P)x, ei⟩ = ⟨x, ei⟩ = 0
N It means, that there exists 0 , x ∈ (I − P) (HN ) such that x ⊥ span {(I − P)ei}i∈S c . As x = i∑=1⟨x, ei⟩(I − P)ei, then for any i ∈ S c. Hence, x = i ∑S⟨x, ei⟩ei, so ∈ ∑⟨x, ei⟩ei = x = (I − P)x = ∑⟨x, ei⟩(I − P)ei, i∈S i∈S i.e. ∑⟨x, ei⟩Pei = 0, and, thus, {Pei}i∈S are linearly dependent.
i∈S
(
i∈S i∈S ⟨x, (I − P)e j⟩ = ⟨(I − P)x, e j⟩ = ⟨∑ biei, e j =
⟩ i∈S ∑ bi⟨ei, e j⟩ = 0, i∈S ＲＱＸ if j ∈ S c. Thus, x⊥span {(I − P)ei}i∈S c , and hence,
Proposition 4. Parseval-Steklov frame is a full spark frame iff Naimark complement of this frame is a full spark frame also.
Proof. By theorem 1, Parseval-Steklov frame can be written as {Pei}iN=1 , where {ei}iN=1 is an ONB in HN and P is the orthogonal projection in HN . Naimark complement for Parseval-Steklov frame looks as {(I − P)ei}iN=1 . By definition {Pei}iN=1 is a full spark frame, if for any S ⊆ {1, . . . , N} with |S | = M {Pei}i∈S is a basis in the range of the projection P. By theorem 3, we have that {(I − P)ei}i∈S c is a basis in the range of the projection I − P, so {(I − P)ei}iN=1 is a full spark frame also. The reverse assertion is proved similarly.
If Parseval-Steklov frame ensures recovery without phases, Naimark complement can not provide recovery without phases. The thing is including, in particular, that in Naimark complement may be insufficient number of vectors.
Proposition 5. If Parseval-Steklov frame {φ n}n=1 ensures recovery without phases in RM, and Naimark comple
N ment to this frame also ensures recovery without phases in RN−M, then
2M − 1 ≤ N ≤ 2M + 1.
Proof. If {φ n}n=1 ensures recovery without phases in RM, then N ≥ 2M − 1 (theorem 2). If Naimark complement
N ensures recovery without phases in RN−M, then N ≥ 2(N − M) − 1, or N ≤ 2M + 1.
But Naimark complement can fail to ensure recovery without phases even under conditions of proposition 3.
Example. Let {φ m}2mM=2 be the full spark frame in RM, M ≥ 3. Let’s put φ 1 = φ 2, and let S be the frame operator for {φ m}2mM=1. Note that {S − 21 φ m}2mM=2 is full spark frame, and ensures recovery without phases. For any partition S, Sc ⊂ {1, . . . , 2M} one of the sets S or Sc has at least M elements from the full spark frame {S − 21 φ m}2mM=2 and hence complete in RM.
Now let’s show, that Naimark complement for {S − 21 φ m}2mM=1 does not ensure recovery without phases. Let’s break {S − 21 φ m}2mM=1 on {S − 21 φ m}2m=1 and {S − 21 φ m}2mM=3 . None of them is linear independent, as φ 1 = φ 2, and M ≥ 3. According to theorem 3, Naimark complements for each of these sets are not comlete in R2M−M = RM. Thus, there is a partition of Naimark complement which contradicts the complement property and does not ensure phaseless recovery.
If Parseval-Steklov frame is full spark frame, then phaseless recovery is inherited by Naimark complement.
N
Proposition 6. If Φ = {φ n}n=1 is full spark Parseval-Steklov frame, 2M − 1 ≤ N ≤ 2M + 1, then Φ ensures phaseless recovery in RM, and Naimark complement for Φ ensures phaseless recovery in RN−M.
Proof. By proposition 2 Naimark complement for Φ is full spark frame in RN−M. We have 2M − 1 ≤ N and 2(N − M) − 1 ≤ N, then, by theorem 2, both Φ and its Naimark complement have complement property in relevant spaces.
Following [4, 10] we define the recovery of a vector-signal by the norms of projections on subspaces. Definition 8. Let {Wn}n=1 be the set of subspaces in HM, let {Pn}n=1 be orthogonal projections on these subspaces.
N N We say, that {Wn}n=1 (or {Pn}nN=1) ensures recovery by the norms of projections, if for any x, y ∈ HM equalities
N ∥Pn x∥ = ∥Pny∥ for n = 1, . . . , N imply x = cy for some c with |c| = 1.
Further such sets of subspaces will be called RNP-sets.
A lot of attention to such recovery is paid in [10]. For one-dimensional subspace Wn the number ∥Pn x∥ can be received only from two vectors ±Pn x. For subspaces Wn with higher dimensions we have continuum of vectors with ∥Pn x∥.
Nevertheless the map
A(x)(n) = ∥Pn x∥ can be injective for subspaces with higher dimensions. The proof of this result uses the scheme of [10], we need some auxiliary assertions.
Let {φ n}n=1 be full spark frame in RM. Let’s define ONB in RM using the following algorithm: ψ1 is a random
N vector, ψ2 is a random vector from [span(ψ1)]⊥ , . . . , ψk is a random vector from [span({ψn}kn−=11)]⊥ . Then {φ n}n=1 ∪ N {ψm}mM=1 is the full spark frame with the probability 1.
Proof.
N k N k+1
Let 1 ≤ k < M. We suppose, that {φ n}n=1 ∪ {ψm}m=1 is full spark frame, we need to check, that {φ n}n=1 ∪ {ψm}m=1 is full spark frame too. For this we have to show that ψk+1 does not lie in the span of any M − 1 vectors from {φ n}n=1 ∪ {ψm}km=1. Choose any M − 1 such vectors and denote them by A. Put Wk := [span({ψm}m=1)]⊥ and pick ψk+1
N k as a random unit norm vector from this (M − k) -dimensional space. Then {φ n}n=1 ∪ {ψm}km+=11 is full spark system ⇔ N ψk+1 < span(A). The last is truly with probability 1 iff
dim (span(A) ∩ Wk) ≤ (M − k) − 1.
as dim (Wk) = M − k. For contradiction, we suppose that
We have further that
In fact, span(A) ∩ Wk is a subset in (M − k) -dimensional space Wk, and so inequality (
Let’s apply the method of mathematical induction. A vector ψ1 is chosen randomly from W0 = RM. If A any M − 1 vectors from {φ n}nN=1, then
dim(span(A) ∩ W0) = M − 1,
N and {φ n}n=1 ∪ ψ1 is full spark frame with probability 1.
N k N Let’s suppose that {φ n}n=1 ∪ {ψm}m=1 is full spark frame. We denote by A any M − 1 vectors from {φ n}n=1 ∪ {ψm}km=1. Let’s consider two possible cases. 1. ψk < A. We have Wk ⊂ Wk−1 and
span(A) ∩ Wk = (span(A) ∩ Wk−1) ∩ Wk.
Note that dim Wk = M − k, dim (span(A) ∩ Wk−1) ≤ M − k, because ψk < A. So for the proof (
2. ψk ∈ A. Let’s note that
Wk⊥ ⊂ [span(A) ∩ Wk−1]⊥ , dim (span(A) ∩ Wk) ≤ M − k, dim (span(A) ∩ Wk) = M − k.
(
dim (span(A \ ψk) ∩ Wk) ≤ dim (span(A \ ψk ∪ φ ) ∩ Wk) ≤ (M − k) − 1.
The last inequality is a result of the first case above.
On the other hand as ψk⊥Wk and ψk ∈ A, we receive from (
dim (span(A \ ψk) ∩ Wk) = dim (span(A) ∩ Wk) = M − k.
This contradiction proves (
Corollary 3. The finite set of ONB, which are built by the algorithm of random choice of lemma 1, is full spark frame with the probability 1.
Proof. Let’s apply consistently the lemma 1.
Lemma 2. For an integer M ≥ 2 let’s pick integers M − 1 ≥ I1 ≥ I2 ≥ . . . ≥ I1 ≥ 1. There is a real invertible M × M-matrix with 0 − 1 instances such that the k-row has exactly Ik ones.
Proof.
We apply induction by M. The claim is obvious for M = 2. Let’s suppose that the assertion is valid for M. Let’s look at the set of M + 1 numbers such that for some s ≤ M + 1. By induction assumption for the set of numbers k-row for k = s + 1, . . . , M. Let’s define (M + 1) × (M + 1)-matrix B = [bi j]iM,j+=11 defining there is the invertible M × M-matrix A = [ai j]iM,j=1 with Ik−1 − 1 = M − 1 ones in k-row for k = 1, . . . , s and Ik ones in M = I1 = . . . = Is > Is+1 ≥ . . . ≥ IM+1 ≥ 1 I1 − 1 = . . . = Is − 1 ≥ Is+1 ≥ . . . ≥ IM ≥ 1
ai j, bi j = 11,, 0,
1 ≤ i, j ≤ M, 1 ≤ i ≤ s, j = M + 1, i = M + 1, 1 ≤ j ≤ M + 1,
for other indexes.
The matrix B has Ik ones in k-row for k = 1, . . . , M + 1. The matrix A = [ai j]iM,j=1 = [bi j]iM,j=1 is invertible, so the matrix B by row reduces can be reduced to the step form Be = [ebi j]iM,j+=11 , where [ebi j]iM,j=1 = IM×M, and the row (M + 1) is not changed. If we suppose that Be is not invertible, then the row (M + 1) by row reduces can be reduced to the zero row and hence ebM+1,l = 1.
If Be is not invertible, then by row reduces the last row is reduced to the zero row, and we have Let’s define for each l ∈ {1, . . . , IM+1} the matrix Bel. It is obtained from the matrix Be changing ebM+1,M+1 = 0 to IM+1 ∑ ebM+1,i = 0. i=1 IM+1 ∑ i=1,i,l
ebM+1,i = −1.
The equality (
Let φ { n}n=1 2M 1 −
∥ · ∥ nality and normalization (
= 1) to the sets φ x
RM
( projections on span φ { n}n∈Ik )
( and span φ
{ n}n∈Jk by P x and P x for k = 1, . . . , 2M
I J k k Let A = [a
M be M
× Similarly we define the matrix B = [b ) −
1. for other z.
RM
RM whence − = ∑ n I ∈ k ∈ ,
P x
I 1 . .
.
P x
I M 2
= A
2
|⟨ 1⟩|
2 . .
. |⟨
M ⟩| . 2 Theorem 6. There exists RNP-set in consisting from 2M − − 1. be the set of vectors in with complement property and with additional requirement of orthogo
M
. The corollary 2 ensures the existence of such set. respectively. The next construction ensures phaseless recovery for M-matrix, its rows are agreed with I , i. e. a k = 1, for z
I , and a k
= 0 for other z.
∈ as (M 1) × (M − = 1 for z + M
J , and b k
= 0 ∈ ( Let’s look at the subspaces span φ { n}n∈Ik ) for k = 1, . . . , M. For x
RM we have N < 2M −
The set φ { n}n=1 2M 1
− ( span φ { n}n∈Ik )
( and span φ { n}n∈Jk
) provide the invertibility of the matrixes A and B.
{|⟨
M n⟩|}n=1 This equation may be solved upon
, if the matrix A is invertible. Similar equation may be written with the matrix B. Hence if the matrixes A and B are invertible, we obtain the complete set of ”measurements” has complement property and according to theorem 2, phaseless recovery is possible using subspaces − for k = 1, . . . , 2M
1. To complete the proof we choose I
Let’s note that the quantity of ones in each row coincides with the dimension of the appropriate subspace. Such selection is possible according to lemma 2 for any subsets I , J , with 1 k k
I ≤ | k| ≤
M −
J ≤ | k| ≤
M 2.
The answer to the next question is unknown [4]: Question. Is it possible phaseless recovery by norms of projections in with the set of subspaces W RM {|⟨ 2M 1
− .
M for
The first author was supported by RFBR grant N 7-01-00138. [7[]6B]oteAlhloe-xAenedvra,dBe.SF,CualslaSzzpaaPrGk,FNrgaumyeensH/VB,T.rAemleaxineJeCv.,PJh.aCsearhetirlile,vDal .veGrs.esMphixasoenles[sErelecocntrstoruncitciorne. sUoRuLr:chet]tp.–s:/A/arcxcive.sosrgm/abosd/1e5:07h.t0t5p8s1:5/./arxiv.org/abs/1110.3548. ＲＲＲ