# On the Uniqueness of the Sparse Signals Reconstruction Based on the Missing Samples Variation Analysis

Authors: Ljubiša Stanković; Miloš Daković
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

An approach to sparse signals reconstruction considering its missing measurements/samples as variables is recently proposed. Number and positions of missing samples determine the uniqueness of the solution. It has been assumed that analyzed signals are sparse in the discrete Fourier transform (DFT) domain. A theorem for simple uniqueness check is proposed. Two forms of the theorem are presented, for an arbitrary sparse signal and for an already reconstructed signal. The results are demonstrated on illustrative and statistical examples.


---

## Body

## 1. Introduction

In many engineering applications, an incomplete set of samples/measurements arises due to physical system constraints. In some cases randomly positioned samples/measurements are heavily corrupted so that it is better to omit them and consider them as unavailable [1, 2]. In these applications reduction of the considered dataset is not a result of an intentional compressive sensing strategy [3–8]. Nevertheless, the primary goal is the signal recovery, as in the compressive sensing theory [8–15]. Recently, an adaptive-step gradient-based method for the reconstruction of sparse signals with missing/omitted samples has been proposed [16]. The proposed method reconstructs the remaining missing samples/measurements in order to make a complete set of samples/measurements, in contrast to the common reconstruction methods that recover the signal in their sparsity domain. The final result in all algorithms is the same. It is full recovery of the signal.In general, the reconstructed signal uniqueness is guaranteed if the restricted isometry property is used and checked with appropriate isometry constants [5]. However, two problems exist in the implementation of this method. For a specific measurement matrix, it produces quite conservative bounds. In practice, it produces a large number of false alarms for nonuniqueness. In addition, uniqueness check with the restricted isometry property requires a combinatorial approach, which is an NP-hard problem (like the solution of the problem itself using the norm-zero in the minimization). In the adaptive gradient-based method, the missing samples/measurements are considered as the minimization variables. The available samples values are known and fixed. Obviously, the number of variables in the minimization process is equal to the number of missing samples/measurements in the observation domain. This approach is possible when the common signal transforms are the domains of signal sparsity. Then missing and available samples/measurements form a complete set of samples/measurements.The discrete Fourier transform (DFT), as the most important signal transform, is considered in this paper as the sparsity domain of the signal. A theorem for the uniqueness of the reconstructed solution, based on the missing sample variations, is presented. Two forms of the theorem are presented: one stating the uniqueness condition for a given missing sample transformation matrix and the other providing the uniqueness check if a sparse signal is already recovered using a reconstruction algorithm. The solution is unique in the sense that the variation of the missing sample values cannot produce another signal of the same or lower sparsity. The theorems provide an easy and computationally efficient uniqueness check.The paper is organized as follows. After the introduction, the uniqueness theorems and corollaries are defined and illustrated on examples. The proofs are presented in Section3. The worst case signal is derived and related to the group delay function in Section 4. Theoretical results are demonstrated on simple illustrative and statistical examples as well.


## 2. On the Reconstructed Signal Uniqueness

Consider a signalx
(
n
) with n
∈
N
=
{
0,1
,
2
,
…
,
N
-
1
}. Assume that Q of its samples at the positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} are missing/omitted. The signal is sparse in the DFT domain, with sparsity s. The reconstruction goal is to get x
(
n
), for all n
∈
N, using available samples at n
∈
M
=
N
∖
N
Q. We will consider a new signal of the form(1)
x
a
n
=
x
n
+
z
n
,where z
(
n
)
≡
0 for the available signal positions n
∈
M and z
(
n
) may take arbitrary values at the positions of missing samples n
=
q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}. The DFT of this signal is (2)
X
a
k
=
X
k
+
Z
k
=
∑
i
=
1
s
σ
i
δ
k
-
k
0
i
+
∑
m
=
1
Q
z
q
m
e
-
j
2
π
q
m
k
/
N
.Positions of nonzero values in X
(
k
) are k
0
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
} with X
(
k
0
i
)
=
σ
i. In the minimization process the values of missing samples of x
a
(
n
)
=
x
(
n
)
+
z
(
n
) for n
∈
N
Q are considered as variables. The goal of the reconstruction process is to get x
a
(
n
)
=
x
(
n
) or z
(
n
)
=
0 for all n
∈
N. This goal should be achieved by minimizing the sparsity of the signal transform X
a
(
k
). The existence of the unique solution of this problem depends on the number of missing samples, their positions, and the signal itself.First, assume that the signal can take any form, including the worst possible one. Then the number of missing samples and their positions will be considered only. The uniqueness, in this case, means that if a signal with the transformX
(
k
) of sparsity s is obtained using a reconstruction method, with a given set of missing samples, then there is no other signal of the same or lower sparsity that satisfies the given set of available samples values, using the same set of missing samples as variables.Theorem 1.
Consider a signalx
(
n
) that is sparse in the DFT domain with unknown sparsity. Assume that the signal length is N
=
2
r samples and that Q samples are missing at the instants q
m
∈
N
Q. Assume that the reconstruction is performed and that the DFT of reconstructed signal is of sparsity s. The reconstruction result is unique if the inequality(3)
s
<
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
sholds. Integers Q
2
h are calculated as(4)
Q
2
h
=
max
b
=
0,1
,
…
,
2
h
-
1
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
h
=
b
.Example. Consider a signal with N
=
2
5
=
32 and Q
=
9 missing samples at(5)
q
m
∈
N
Q
=
2,3
,
8,13,19,22,23,28,30
.Using the theorem, we will find the sparsity limit s when we are able to claim that the reconstructed sparse signal is unique for any signal form.(i) Forh
=
0, we use Q
2
0
=
Q and get 2
0
Q
2
0
-
1
-
1
=
(
Q
-
1
)
-
1
=
9.(ii) Forh
=
1, the number Q
2
1 is the greater value of (6)
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
0
=
card
⁡
2,8
,
22,28,30
=
5
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
1
=
card
⁡
3,13,19,23
=
4
,that is, the maximal number of even or odd positions of missing samples. Thus Q
2
1
=
max
⁡
5,4
=
5 with 2
1
Q
2
1
-
1
=
8.(iii) NextQ
2
2 is calculated as the maximal number of missing samples whose distance is multiple of 4. For various initial counting positions b
=
0,1
,
2,3 the numbers of missing samples with distance being multiple of 4 are 2,1
,
3, and 3, respectively. Then Q
2
2
=
max
⁡
2,1
,
3,3
=
3 with 2
2
(
Q
2
2
-
1
)
=
8
.(iv) ForQ
2
3 the numbers of missing samples at distances being multiple of 8 are found for various b
=
0,1
,
2,3
,
4,5
,
6,7. The value of Q
2
3 is 2 with 2
3
(
Q
2
3
-
1
)
=
8.(v) Finally we have two samples at distance16 (samples at the positions q
2
=
3 and q
5
=
q
2
+
N
/
2) producing Q
2
4
=
Q
16
=
2 with 2
4
(
2
-
1
)
=
16.The reconstructed signal of sparsitys is unique if (7)
s
<
N
-
max
h
=
0,1
,
2,3
,
4
⁡
2
h
Q
2
h
-
1
-
s
s
<
32
-
max
⁡
9,8
,
8,8
,
16
-
s
s
<
32
-
16
-
sor(8)
s
<
8
.The theorem considers general signal form. It includes the case when the amplitudes of signal components are related to each other and related to the missing sample positions. The specific signal form required by the theorem, to reach its bound, is analyzed in Section4. Since this kind of relation is a zero-probability event, we will define a corollary, neglecting the probability that the signal values are dependent on each other and related to missing sample positions at the same time.Corollary 2.
Consider a signalx
(
n
) that is sparse in the DFT domain. Assume that the signal length is N
=
2
r samples and that Q samples are missing at the instants q
m
∈
N
Q. Also assume that the reconstruction is performed and that the DFT of reconstructed signal is of sparsity s. Assume that the amplitudes of signal components are arbitrary with arbitrary phases so that the case when all of them can be related to the values defined by using the missing sample positions is a zero-probability event. The reconstruction result is not unique if the inequality(9)
s
≥
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
1holds. Integers Q
2
h are calculated in the same way as in Theorem 1.Example. Consider a signal with N
=
2
5
=
32 and Q
=
9 missing samples at(10)
q
m
∈
N
Q
=
2,3
,
8,13,19,22,23,28,30
.The sparsity limit s when we are able to claim that the reconstructed sparse signal is not unique is (11)
s
≥
N
-
max
h
=
0,1
,
2,3
,
4
⁡
2
h
Q
2
h
-
1
-
1
s
≥
32
-
max
⁡
9,8
,
8,8
,
16
-
1
s
≥
15
.Pseudocode for uniqueness check according to Theorem1 and Corollary 2 is presented in Algorithm 1. Note that in Corollary 2 we used the condition that the reconstruction result is nonunique (instead of the condition that the reconstruction result is unique in Theorem 1) since the zero-probability events are included here.Algorithm 1:Sparsity limits—Theorem 1 and Corollary 2.
Require:
(i) Set of missing sample positionsN
Q
(ii) Total number of signal samplesN, N
=
2
r
(1)K
T
←
N
(2)K
C
←
N
(3)for
h
←
1
,
r
-
1
do
(4)for
b
←
0
,
2
h
-
1
do
(5)Q
b
←
c
a
r
d
q
:
q
∈
N
Q and mod
⁡
q
,
2
h
=
b
(6)end for
(7)Q
2
h
←
max
b
⁡
Q
b
(8)if
K
T
>
(
N
-
2
h
(
Q
2
h
-
1
)
)
/
2
then                ⊳ Theorem 1 check
(9)K
T
←
(
N
-
2
h
(
Q
2
h
-
1
)
)
/
2
(10)end if
(11)if
K
C
>
N
-
2
h
(
Q
2
h
-
1
)
-
1
then                ⊳ Corollary 2 check
(12)K
C
←
N
-
2
h
(
Q
2
h
-
1
)
-
1
(13)end if
(14)end for
Output:     K
T, K
C
(i) Every solution with sparsitys
<
K
T is unique.
(ii) Solution with sparsitys
<
K
C is unique with probability one, excluding zero-probability event
(when the amplitudes of signal components are related to each other with a relation defined by
the missing sample positions).Corollary2 provides the uniqueness test for the given positions of unavailable samples. In the cases with h
>
0 it exploits the periodic structure of the transformation matrix of missing samples. The periodical form assumes that the positions of possible zero values in Z
(
k
) do not interfere with the signal nonzero value positions. This is possible in the worst case analysis. For example, with two missing samples at the positions z
(
q
m
) and z
(
q
m
+
N
/
2
), the reconstruction process assumes that there are N
/
2
-
1 zero values in Z
(
k
) and that the same number of zero values is preserved in X
(
k
)
+
Z
(
k
). This event can occur if we assume that all nonzero values of X
(
k
) have the same structure as Z
(
k
). In this specific case, it means that all of the signal nonzero coefficients are either on odd or even positions in the frequency domain.Numerical Example. Signal with N
=
64 samples is considered. The signal sparsity is varied from s
=
1 to s
=
N
-
1. For each signal sparsity s the number of missing samples is varied from Q
=
1 to Q
=
N
-
1. For each pair (
s
,
Q
) 1000 trials are performed with Q randomly positioned missing samples. Uniqueness is checked by Theorem 1 and Corollary 2. Percentage of trials where uniqueness is guaranteed is presented in Figure 1. We can clearly see two regions: one where uniqueness was achieved in each trial (P
=
100
%) and the other where the solution was always nonunique (P
=
0
%). In the transition between these two regions the uniqueness highly depends on the missing sample positions, producing 0
%
<
P
<
100
%.Figure 1
Uniqueness probability calculated for various sparsitys and the number of available samples (
N
-
Q
) by using Theorem 1 (a) and Corollary 2 (b) in 1000 random realizations. Lines s
=
N
-
Q and s
=
(
N
-
Q
)
/
2 are presented as guidelines. In this case the uniqueness is checked without using information about nonzero DFT coefficient positions in the reconstructed signal.
(a)
(b)We see that there is a sharp transition, for example, atQ
=
16 (for N
-
Q
=
48), from P
(
s
,
Q
)
=
P
(
15,16
)
≅
1 when s
=
15 to P
(
s
,
Q
)
=
P
(
16,16
)
≅
0 for s
=
16 (marked with white dots in Figure 1(a)). It means that the difference of probabilities P
(
15,16
)
-
P
(
16,16
) is almost 1. Let us explain this effect. Consider Theorem 1 condition s
<
N
-
2
h
Q
2
h
-
1
-
s for h
=
0,1
,
…
,
r
-
1. If 32
=
64
-
2
h
Q
2
h
-
1, the solution will be unique for s
=
15 and nonunique for s
=
16. This equality is satisfied for Q
32
=
2, Q
16
=
3, Q
8
=
5, and Q
4
=
9. It means that at least one of the following holds: (1) there are Q
32
=
2 samples at distance 32, (2) there are Q
16
=
3 samples at the distance being multiple of 16, (3) there are Q
8
=
5 samples at the distance being multiple of 8, and (4) there are Q
4
=
9 samples at the distance being multiple of 4. The probability that among Q
=
16 samples out of N
=
64 there are 2 samples at the distance 32 is P
=
0.92. Since other events are with lower probabilities, this one is sufficient to explain the sharp change in P
(
s
,
Q
). We may write P
15,16
-
P
16,16
~
0.92.After signal reconstruction, we are in a position to additionally specify the uniqueness requirements using the reconstructed signal. When a sparse signal is reconstructed we want to check the uniqueness of this signal. It means that the signalx
(
n
), with its transform X
(
k
) which is nonzero at k
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
}, is obtained and we want to check if there is another signal X
(
k
)
+
Z
(
k
) with the same or lower sparsity, where Z
(
k
) is the DFT of arbitrary values of samples at the missing sample positions. The positions of nonzero values in X
(
k
) are not arbitrary, while the positions of zero and nonzero values in Z
(
k
) could change to produce minimal possible sparsity of X
(
k
)
+
Z
(
k
). In the previous example with two missing samples z
(
q
m
) and z
(
q
m
+
N
/
2
), when the signal is already recovered, it means that we can not assume that all {
k
01
,
k
02
,
…
,
k
0
s
} are either odd or even. They are given since we have already reconstructed a sparse signal.Theorem 3.
Consider a signalx
(
n
) that is sparse in the DFT domain with unknown sparsity. Assume that the signal length is N
=
2
r samples and that Q samples are missing at the instants q
m
∈
N
Q. Also assume that the reconstruction is performed and that the DFT of reconstructed signal is of sparsity s. Assume that the positions of the reconstructed nonzero values in the DFT are k
0
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
}. Reconstruction result is unique if the inequality(12)
s
<
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
s
+
2
S
2
r
-
hholds. Integers Q
2
h and S
2
r
-
h are calculated as (13)
Q
2
h
=
max
b
=
0,1
,
…
,
2
h
-
1
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
h
=
b
S
2
r
-
h
=
∑
l
=
1
Q
2
h
-
1
P
h
l
P
h
l
=
sort
b
=
0,1
,
…
,
2
r
-
h
-
1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
r
-
h
=
b
,where P
h
(
1
)
≤
P
h
(
2
)
≤
⋯
≤
P
h
(
2
r
-
h
).Note that forS
2
r
-
h
=
0 this theorem reduces to Theorem 1. For the DFT values equally distributed over all positions, this theorem produces result close to s
≥
N
-
Q
.Corollary 4.
Consider a signalx
(
n
) that is sparse in the DFT domain with unknown sparsity. Assume that the signal length is N
=
2
r samples and that Q samples are missing at the instants q
m
∈
N
Q. Also assume that the reconstruction is performed and that the DFT of reconstructed signal is of sparsity s. Assume that the positions of the reconstructed nonzero values in the DFT are k
0
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
}. Assume that the amplitudes of signal components are arbitrary with arbitrary phases so that the case when all of them can be related to the values defined by using the missing sample positions is a zero-probability event. Reconstruction result is not unique if the inequality(14)
s
≥
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
1
+
S
2
r
-
hholds. Integers Q
2
h and S
2
r
-
h are calculated as in Theorem 3. The case when all of signal components can be related to the values defined by using the missing sample positions is considered here.Pseudocode for uniqueness check according to Theorem3 and Corollary 4 is presented in Algorithm 2.Algorithm 2:Uniqueness check—Theorem 3 and Corollary 4.
Require:
(i) Set of missing sample positionsN
Q
(ii) Set of nonzero values in the reconstructed DFTK
s
(iii) Total number of signal samplesN, N
=
2
r
(1)R
1
←
1
(2)R
2
←
1
(3)K
←
c
a
r
d
K
s
(4)for
h
←
1
,
r
-
1
do
(5)for
b
←
0
,
2
h
-
1
do
(6)Q
b
←
c
a
r
d
q
:
q
∈
N
Q and mod
⁡
(
q
,
2
h
)
=
b
(7)end for
(8)Q
2
h
←
max
b
⁡
Q
b
(9)for
b
←
0
,
2
r
-
h
-
1
do
(10)P
b
←
c
a
r
d
k
:
k
∈
K
s and mod
⁡
(
k
,
2
r
-
h
)
=
b
(11)end for
(12) Sort arrayP in non-decreasing order
(13)S
2
r
-
h
←
∑
l
=
1
Q
2
h
-
1
P
s
o
r
t
e
d
(
l
)
(14)if
K
≥
N
-
2
h
(
Q
2
h
-
1
)
-
K
+
2
S
2
r
-
h
then                 ⊳ Theorem 3 check
(15)R
2
←
0
(16)end if
(17)if
K
≥
N
-
2
h
(
Q
2
h
-
1
)
-
1
+
S
2
r
-
h
then                 ⊳ Corollary 4 check
(18)R
1
←
0
(19)end if
(20)end for
(21)R
←
R
1
+
R
2
Output: R
(i)R
=
2 when the considered solution is unique.
(ii)R
=
1 when the considered solution is unique with probability one excluding zero-probability event
(when amplitudes of the signal components are related to each other with a relation defined by
missing sample positions).
(iii)R
=
0 when the considered solution is not unique.Example. Consider a signal with N
=
32 and Q
=
9 missing samples at(15)
q
m
∈
N
Q
=
2,3
,
8,13,19,22,23,28,30
.Assume that with these missing samples we have reconstructed signals with nonzero DFT values at the positions (a)
(16)
K
s
=
1,3
,
5,7
,
9,11,13,15,17,21,23,25,27,29,31
,
(b)
(17)
K
s
=
1,3
,
5,9
,
13,17,21,29,31,2
,
4,8
,
12,16,20,24,30
.By testing these two signals, we get the following decisions. According to Theorem 1 we cannot claim uniqueness in either of these cases since s
=
15 in the first case and s
=
17 in the second case. Both are greater than Theorem 1 bound s
<
8. The same holds for Corollary 2 since both are s
≥
15. By testing these results with Theorem 3 we get that in case (a) the solution is nonunique. It is due to a very specific form of the reconstructed signal with all components being found at the odd frequency positions. Since the sparsity was defined by periodicity 16 in q
m
∈
N
Q, then variations of two signal samples z
(
q
2
=
3
) and z
(
q
5
=
19
) can produce a signal X
(
k
)
+
Z
(
k
) with the same sparsity as the reconstructed signal. These two samples, as variables, are able to produce many (
N
/
2
) zero values in Z
(
k
) either at odd or even positions in frequency (Section 4). In this case, they are at even positions of X
(
k
)
+
Z
(
k
). However, in signal (b) that is not the case. Nonzero values are distributed over both even and odd frequency positions. Although sparsity of this signal is s
=
17 the reconstruction is unique. The distribution of nonzero values in the reconstructed X
(
k
) is such that by varying two samples z
(
q
2
=
3
) and z
(
q
5
=
19
) we cannot produce a signal X
(
k
)
+
Z
(
k
) of the same or lower sparsity with nonzero z
(
q
2
=
3
) and z
(
q
5
=
19
). The limit, in this case, is defined by the lower periodicity in z
(
q
) than N
/
2. Thus, if we obtain this signal using a reconstruction algorithm the solution is unique.Example. Consider a signal with N
=
1024 and Q
=
512 missing samples at q
m
∈
N
Q
=
{
0,2
,
4
,
…
,
1022
}. The reconstructed signal is at the frequencies (a) K
s
=
{
3
}, (b) K
s
=
{
3,515
}. We can easily check that in all cases with Theorem 1, Corollary 2, and Theorem 3, the reconstruction is nonunique although s
=
1 or s
=
2 is much smaller than the available number of samples N
-
Q
=
512. The answer is obtained almost immediately, since the computational complexity of Theorem 1, Corollary 2, and Theorem 3 is of order O
(
N
).Numerical Example. Signal with N
=
64 samples is considered. The signal sparsity is varied from s
=
1 to s
=
N
-
1. For each signal sparsity s the number of missing samples is varied from Q
=
1 to Q
=
N
-
1. For each pair (
s
,
Q
) 1000 trials are performed with randomly positioned s nonzero DFT values and randomly positioned Q missing samples. In each trial the uniqueness is checked by Theorem 3 and Corollary 4. Percentage of trials where the uniqueness is guaranteed is presented in Figure 2. We can clearly see two regions: one where the uniqueness was achieved in each trial (P
=
100
%) and the other region where the solution was nonunique in each trial (P
=
0
%). The transition between regions is quite sharp. In this transition region, for given (
s
,
Q
), the uniqueness highly depends on the positions of DFT values and missing samples producing 0
%
<
P
<
100
%. The transition region is wider for Theorem 3 comparing to transition region for Corollary 4.Figure 2
Uniqueness probability calculated for various sparsitys and the number of available samples (
N
-
Q
) by using Theorem 3 (a) and Corollary 4 (b) in 1000 random realizations. In this case the uniqueness is checked after reconstruction using information about nonzero DFT coefficient positions in the reconstructed signal.
(a)
(b)In Figure3, regions where the probability is higher than 99% are presented. The first region is defined by Theorem 3, which guarantees uniqueness for any signal. The second region is defined by Corollary 4 and it guarantees uniqueness with a high probability (this region is signal dependent). These regions are combined in the third subplot.Figure 3
Regions with uniqueness probability greater than 99% for various sparsitys and the number of available samples (
N
-
Q
) obtained with Theorem 3 (a), Corollary 4 (b) and combined regions (c) in 1000 random realizations. Lines s
=
N
-
Q and s
=
(
N
-
Q
)
/
2 are presented as guidelines.
(a)
(b)
(c)


## 3. Proofs of the Theorems and Corollaries

### 3.1. Proof of Theorem1

Consider the DFT of a signalx
(
n
) with N samples. For the presentation simplicity we assumed common N
=
2
r although the results can be generalized for any N. Assume that M available samples are at the instants n
i
∈
M
=
{
n
1
,
n
2
,
…
,
n
M
} and the missing samples are at the instants q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} and Q
=
N
-
M. Assume that the reconstruction process is done and the obtained signal is sparse in the DFT domain. Its sparsity is s with nonzero coefficients k
0
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
}
⊂
{
0,1
,
…
,
N
-
1
}. Under this assumption the signal x
(
n
) is(18)
x
n
=
∑
i
=
1
s
1
N
σ
i
e
j
2
π
n
k
0
i
/
N
.Amplitudes σ
i
/
N of the signal components are arbitrary with arbitrary phases arg
⁡
σ
i.Let us form a signal(19)
x
a
n
=
x
n
+
z
n
,where z
(
n
)
=
0 for n
∈
M and takes arbitrary values z
(
q
m
) at the positions of missing samples q
m
∈
N
Q. The DFT of this signal is(20)
X
a
k
=
∑
i
=
1
s
σ
i
δ
k
-
k
0
i
+
∑
m
=
1
Q
z
q
m
e
-
j
2
π
q
m
k
/
N
.Denote the number of nonzero values in X
a
(
k
) as X
a
0. The DFT of signal z
(
n
) is(21)
Z
k
=
DFT
z
n
=
∑
m
=
1
Q
z
q
m
e
-
j
2
π
q
m
k
/
N
.Denote the number of nonzero values in Z
(
k
) by N
Z
=
Z
0. The aim of minimization of X
a
0 is to produce the smallest possible value X
a
0
=
s. If this is possible in trivial case z
(
n
)
=
0 only, then our solution is unique. If there exists a nontrivial solution for z
(
n
) with X
a
0
=
s, then we have two different solutions x
(
n
) and x
(
n
)
+
z
(
n
) with the same sparsity s meaning that our solution is not unique.The DFT of signalz
(
n
) can be written in a matrix form as(22)
1
1
⋯
1
e
-
j
2
π
q
1
/
N
e
-
j
2
π
q
2
/
N
⋯
e
-
j
2
π
q
Q
/
N
⋯
⋯
⋯
⋯
e
-
j
2
π
q
1
N
-
1
/
N
e
-
j
2
π
q
2
N
-
1
/
N
⋯
e
-
j
2
π
q
Q
N
-
1
/
N
z
q
1
z
q
2
⋯
z
q
Q
=
Z
0
Z
1
⋯
Z
N
-
1
.Since we look for zeros inZ
(
k
), without loss of generality, we can rewrite system (22) in the form normalized with the first column corresponding to q
1 as(23)
1
1
⋯
1
1
e
-
j
2
π
q
12
/
N
⋯
e
-
j
2
π
q
1
Q
/
N
⋯
⋯
⋯
⋯
1
e
-
j
2
π
q
12
N
-
1
/
N
⋯
e
-
j
2
π
q
1
Q
N
-
1
/
N
z
q
1
z
q
2
⋯
z
q
Q
=
Z
0
Z
1
e
j
2
π
q
1
/
N
⋯
Z
N
-
1
e
j
2
π
q
1
N
-
1
/
N
,where(24)
q
1
n
=
q
n
-
q
1
.In general, during the minimization, we haveQ variables z
(
q
m
) (Q degrees of freedom). First assume that there is no common period (smaller than N) in columns of the transform matrix for the missing sample positions q
i. This case corresponds to pairwise coprime numbers q
12
,
q
13
,
…
,
q
1
Q. Then Q variables z
(
q
m
) can be used to produce Q
-
1 zeros in Z
(
k
) at the positions where there is no signal and, in the worst possible case, to cancel out all s nonzero coefficients in X
(
k
). Therefore the largest possible number of zero values in X
(
k
)
+
Z
(
k
) is (
Q
-
1
)
+
s. The lowest possible number of nonzero values in X
(
k
)
+
Z
(
k
) is N
-
(
Q
-
1
)
-
s. If(25)
N
-
Q
-
1
-
s
>
s
,then the considered solution is unique since only the trivial solution z
(
n
)
=
0 results in sparsity s and every nontrivial solution results in X
a
0
>
s. If we obtain the reconstructed signal with sparsity(26)
s
≥
N
-
Q
+
1
2
,then the solution is not unique. However, if 2
s
<
N
-
Q
+
1, then it still does not mean that the solution is unique since we assumed that there is no periodicity in transform matrix (23). Next we will include all possible cases when some of the columns of transform matrix in (23) may have a common period lower than N.The matrix of coefficientsZ
(
k
) cannot be periodic with period smaller than Q. Thus, with regard to the period of the whole matrix, the worst case would be the transformation matrix which repeats after exactly Q rows, where Q is divisor of N. Denote the number of repetitions by R
=
N
/
Q.For periodic structure of transformation matrix in (23), with such a period that the rows are repeated R times within N, the largest number of zero values in Z
(
k
) is now R
(
Q
-
1
). In addition, the nonzero values in Z
(
k
), in the worst possible case, can cancel all s nonzero DFT values of X
(
k
). Thus, in this case, the lowest possible number of nonzero values in X
(
k
)
+
Z
(
k
) is N
-
R
(
Q
-
1
)
-
s. For the unique solution it should be greater than the signal sparsity; that is, N
-
R
(
Q
-
1
)
-
s
>
s or N
/
(
2
Q
)
>
s. This is the result of the uncertainty principle in the DFT, presented in Section 3.2.The process does not end here. In the minimization process, we must also consider all subsets of missing samplesq
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}. Namely, it can happen that the worst case regarding the maximal number of zero values in Z
(
k
) is not the case with the full set of variables z
(
q
). It could happen that some subsets of the variables q
m
∈
N
Q may produce a higher number of zero values in Z
(
k
) than the whole set of variables. It means that the reconstruction algorithm may find some variables z
(
q
i
) to be zero valued and vary only a subset of remaining variables z
(
q
i
).Subsets of Missing Samples. We have concluded that the periodicity R reduces the sparsity of X
(
k
)
+
Z
(
k
), by increasing the number of possible zero values in Z
(
k
). Consider a general set of missing sample positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}. Then the algorithm for uniqueness should check periods for all possible subsets of missing samples. Assuming as in Theorem 1, without loss of generality, that N
=
2
r the cases are as follows.(1) Using all missing samples, assuming that there is no common period for all of them (in the sense of (23)), the unique solution is obtained if s
<
N
-
(
Q
-
1
)
-
s. The cases with periodic matrix structure will be included in the steps that follows.(2) Consider minimal possible number of periodsR
>
1 for N
=
2
r. It is R
=
2 repetitions in the matrix of coefficients (23) with period N
/
2. Any subset of N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} containing only even or only odd positions can be considered as a set of minimization variables with period N
/
2. The number of missing samples q
m
∈
N
Q at even positions can be written as(27)
N
E
=
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
0
.The same should be done for odd positions in q
m
∈
N
Q:(28)
N
O
=
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
1
.Since we look for the worst case in our reconstruction algorithm, we choose the set with more variables (more degrees of freedom). It is(29)
Q
2
=
max
b
=
0,1
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
b
.Since the number of periods in matrix of coefficients is 2 for these two subsets of missing samples, it means that at most(30)
2
Q
2
-
1zero values can be produced in Z
(
k
). It can be larger than (
Q
-
1
). Therefore beside the condition s
<
N
-
(
Q
-
1
)
-
s considered in step (1) we have also to check(31)
s
<
N
-
2
Q
2
-
1
-
sand use the worst case as the limit for s. It means that, at this point, we should compare Q and 2
Q
2
-
1.Note that the largest possibleQ
2 is Q
2
=
N
/
2. In this case, the solution is unique if(32)
2
s
<
N
-
N
+
1
=
1
.This corresponds to the case when all even (or all odd) signal samples are missing. Then we cannot uniquely reconstruct a signal even for sparsity s
=
1.(3) This analysis should be continued for all possible periods inN. For N
=
2
r the next possible period is N
/
4 with the number of periods R
=
4. Coefficients in the matrix (23) are periodic with N
/
4 if the distance between missing samples is four. Thus, we should divide the set of all missing sample positions N
Q into subsets where distances between q
i are multiples of 4, that is, when mod
⁡
(
q
i
,
4
) is a constant. There are 4 such subsets obtained for mod
⁡
(
q
i
,
4
)
=
b, where b
=
0,1
,
2,3. In the same way as in step (2), denote the cardinality of the largest subset by Q
4:(33)
Q
4
=
max
b
=
0,1
,
2,3
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
4
=
b
.If we find Q
4 such that(34)
4
Q
4
-
1
>
2
Q
2
-
1
,
4
Q
4
-
1
>
Q
-
1
,then it means that in z
(
n
) we can consider as variables (nonzero values) only the samples from the set containing q
i such that mod
⁡
(
q
i
,
4
)
=
b producing Q
4. Then the unique solution is obtained only if(35)
s
<
N
-
4
Q
4
-
1
-
s
.The worst case is when the positions of all missing samples are such that Q
4
=
N
/
4. Then the solution is unique if s
<
2. In the worst case with as many as 3
N
/
4 of available samples (Q
=
Q
4
=
N
/
4) we may reconstruct only signals with sparsity s
=
1.(4) Next possible period forN
=
2
r is N
/
8. The periodicity with period 8 should be considered for any subset of q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} calculating(36)
Q
8
=
max
b
=
0,1
,
2,3
,
4,5
,
6,7
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
8
=
b
.If(37)
8
Q
8
-
1
>
max
⁡
Q
-
1
,
2
Q
2
-
1
,
4
Q
4
-
1
,then the sparsity further reduces to(38)
s
<
N
-
8
Q
8
-
1
-
s
.The worst case when the positions of all missing samples are such that Q
8
=
N
/
8 the solution is unique for s
<
4. In this case even with 7
N
/
8 of available samples we may reconstruct only the signals with sparsity s
=
1,2
,
3.(5) The process should continue for all possible periods2
h
<
N, h
=
4,5
,
…
,
r
-
1. We should calculate(39)
Q
2
h
=
max
b
=
0,1
,
…
,
2
h
-
1
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
h
=
b
.If it is such that(40)
2
h
Q
2
h
-
1
>
max
⁡
Q
-
1
,
2
Q
2
-
1
,
4
Q
4
-
1
,
…
,
2
h
-
1
Q
2
h
-
1
-
1
,then the sparsity constraint for uniqueness is(41)
s
<
N
-
2
h
Q
2
h
-
1
-
s
.(6) Summing up all the cases we get the theorem result that the uniqueness condition is(42)
s
<
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
s
.In the final stage if just two special samples(43)
q
i
∈
N
Q
,
q
i
+
N
/
2
∈
N
Qare missing, then Q
2
r
-
1
-
1
=
1 with the solution being nonunique if(44)
s
≥
N
-
N
2
-
s
.Thus special positions of two missing samples reduce the maximal number of components that can uniquely be detected to N
/
4
-
1.(7) This kind of proof can be generalized for any signal lengthN with possible periods of matrix obtained as divisors of N.


### 3.2. Uncertainty Principle and Theorem1 Bounds

The bounds for sparsity are compared with the results following from the uncertainty relation for the DFT(45)
Q
·
N
Q
≥
N
,where the number of nonzero values in z
(
q
) is denoted by Q and the number of the nonzero values in its DFT Z
(
k
) is N
Q. In the worst case, for a given Q and for the worst possible distribution of positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}, we have(46)
N
Q
=
N
Q
.Consider first the case when we cannot exclude the possibility that the signal DFT assumes values related to the missing sample positions and the worst possible distribution of positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}. The maximal number of nonzero values is N
Q. In the worst case s of nonzero signal DFT values can cancel s nonzero values in Z
(
k
) meaning that the minimal number of nonzero values, in the worst case, is N
Q
-
s. Since it should not be the solution of our minimization problem, the case with all z
(
q
), producing the signal and its sparsity should be lower: N
Q
-
s
>
s or(47)
s
<
N
Q
2
=
N
2
Q
.For arbitrary signal whose values cannot be described by the missing sample positions and for the worst possible distribution of positions we getN
Q
-
1
>
s or(48)
s
<
N
-
Q
Q
=
N
Q
-
1
.These two cases are obtained through the previous analysis as the special worst cases of Theorem1 and Corollary 2 as well.


### 3.3. Proof of Corollary2

In Theorem1 we assumed that Z
(
k
) takes the maximal possible number of Q
-
1 zero values and that at the same time the remaining nonzero values of Z
(
k
) cancel out all signal components X
(
k
). This assumption is very unlikely since after we assumed the maximal possible number of Q
-
1 zeros in Z
(
k
), we have only one remaining degree of freedom. It means that we can cancel out one signal component with one remaining variable and we assume that all other components have specific values so that they will also be canceled out. Consider now the case when signal components are not adjusted to these fixed values of Z
(
k
). Then, in reality, we can expect to cancel out only one component in X
(
k
) with one variable. Repeating Theorem 1 proof with(49)
s
≥
N
-
2
h
Q
2
h
-
1
-
1for nonuniqueness instead of s
<
N
-
2
h
Q
2
h
-
1
-
s for uniqueness produces the proof of Corollary 2.


### 3.4. Proof of Theorem3

Here we will start with two missing samplesq
m
1 and q
m
2 at the distance q
m
1
-
q
m
2
=
N
/
2
=
2
r
-
1
=
2
h. The worst case is Q
2
h
-
1
=
1 with the uniqueness condition(50)
s
<
N
-
N
2
-
1
=
N
2
-
1
.These special positions of two missing samples reduce the maximal number of components that can uniquely be detected to s
=
N
/
2
-
2. However in this case the positions of nonzero DFT values k
0
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
} should be very specific. All of them should be on either even or odd positions, producing(51)
S
2
r
-
h
=
S
2
1
=
min
b
=
0,1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
=
b
=
min
⁡
0,2
=
0
.If that is not the case, then(52)
S
2
1
=
min
b
=
0,1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
=
b
=
min
⁡
1,1
=
1
>
0will reduce the count of zero values that can be achieved in the worst case in X
(
k
)
+
Z
(
k
). Since S
2 of the signal nonzero coefficients are not at the positions of nonzero values of Z
(
k
) then, in the best possible case, only (
s
-
S
2
) out of s nonzero values of the DFT can be canceled out by the predetermined missing sample values (as in Theorem 1). In addition to N
-
2
r
-
1
Q
2
r
-
1
-
1
-
(
s
-
S
2
) nonzero values of X
(
k
)
+
Z
(
k
) at the nonzero positions of Z
(
k
), there are S
2 nonzero values of X
(
k
) positioned at the zero-value positions of Z
(
k
). They cannot be canceled by Z
(
k
). The uniqueness condition for h
=
r
-
1 will therefore require (53)
s
<
N
-
2
r
-
1
Q
2
r
-
1
-
1
-
s
-
S
2
1
+
S
2
1
s
<
N
-
2
h
Q
2
h
-
1
-
s
-
S
2
r
-
h
+
S
2
r
-
h
.This correction of the uniqueness condition with S
2
1 should be done only if Q
2
h
=
Q
N
/
2
=
Q
2
r
-
1
=
2. Denote by P
h
(
l
) the sorted array(54)
P
h
l
=
sort
b
=
0,1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
r
-
h
=
b
.The correction S
2
1
=
S
2
r
-
h with h
=
r
-
1 can be calculated as(55)
S
2
r
-
h
=
∑
l
=
1
Q
2
h
-
1
P
h
l
.For Q
2
h
=
Q
2
r
-
1
=
Q
N
/
2
=
1 (when there are no two samples at the distance N
/
2) the upper summation limit will be 0 and this kind of correction will not be done; S
2
1
=
0. Note that the sum of all P
h
(
l
), l
=
1,2
,
…
,
2
r
-
h is equal to the signal sparsity s.In the same way, forh
=
r
-
2 (missing samples at a distance being multiple of N
/
4) the period of Z
(
k
) is 4. In the worst case when Q
N
/
4
=
Q
2
r
-
2
=
4, the maximal number of nonzero values in X
(
k
) at a distance being multiple of 4 can be canceled out (with nonzero values of Z
(
k
)). The remaining nonzero values in the DFT of signal will be on the zero positions of Z
(
k
) and cannot be canceled out. Note that if Q
N
/
4
=
Q
2
r
-
2
=
3, then two nonzero values in Z
(
k
) will remain (with 3 variables we can make only 2 zero values in each period of Z
(
k
)). The total number of the nonzero values of X
(
k
) that can be canceled is the sum of the two largest numbers in P
h
(
l
) defined by P
h
(
4
)
+
P
h
(
3
)
=
s
-
P
h
(
1
)
-
P
h
(
2
), where(56)
P
h
l
=
sort
b
=
0,1
,
2,3
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
4
=
b
.The number of remaining nonzero DFT values that cannot be canceled out is(57)
S
2
2
=
P
h
1
+
P
h
2
=
∑
l
=
1
Q
2
r
-
2
-
1
P
h
l
.Note that if Q
2
h
=
Q
N
/
4
=
Q
2
r
-
2
=
2, then three nonzero values exist in one period of Z
(
k
) (only one zero value of Z
(
k
) can be obtained within a period) meaning that the total number of signal values that can be canceled out is P
h
(
4
)
+
P
h
(
3
)
+
P
h
(
2
)
=
s
-
P
h
(
1
). The number of remaining nonzero values of X
(
k
) is S
2
2
=
P
h
(
1
)
=
∑
l
=
1
Q
2
r
-
2
-
1
‍
P
h
(
l
).The uniqueness condition is that(58)
s
<
N
-
2
h
Q
2
h
-
1
-
s
-
S
2
r
-
h
+
S
2
r
-
hwith (59)
P
h
l
=
sort
b
=
0,1
,
2
,
…
,
2
r
-
h
-
1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
r
-
h
=
b
S
2
r
-
h
=
∑
l
=
1
Q
2
h
-
1
P
h
l
,and 2
r
-
h
=
4 for h
=
r
-
2. The same analysis is done for all h, using (58)-(59). The value of s satisfying (58) for all h produces Theorem 3 statement.


### 3.5. Proof of Corollary4

This corollary follows from Theorem3 neglecting the probability that several DFT coefficients can be canceled out by predetermined values of the missing samples. Then instead of (
s
-
S
2
r
-
h
) in (58) we have just one sample and(60)
s
≥
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
1
+
S
2
r
-
his used for nonuniqueness instead of the uniqueness condition(61)
s
<
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
s
-
S
2
r
-
h
+
S
2
r
-
h
.


## 3.1. Proof of Theorem1

Consider the DFT of a signalx
(
n
) with N samples. For the presentation simplicity we assumed common N
=
2
r although the results can be generalized for any N. Assume that M available samples are at the instants n
i
∈
M
=
{
n
1
,
n
2
,
…
,
n
M
} and the missing samples are at the instants q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} and Q
=
N
-
M. Assume that the reconstruction process is done and the obtained signal is sparse in the DFT domain. Its sparsity is s with nonzero coefficients k
0
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
}
⊂
{
0,1
,
…
,
N
-
1
}. Under this assumption the signal x
(
n
) is(18)
x
n
=
∑
i
=
1
s
1
N
σ
i
e
j
2
π
n
k
0
i
/
N
.Amplitudes σ
i
/
N of the signal components are arbitrary with arbitrary phases arg
⁡
σ
i.Let us form a signal(19)
x
a
n
=
x
n
+
z
n
,where z
(
n
)
=
0 for n
∈
M and takes arbitrary values z
(
q
m
) at the positions of missing samples q
m
∈
N
Q. The DFT of this signal is(20)
X
a
k
=
∑
i
=
1
s
σ
i
δ
k
-
k
0
i
+
∑
m
=
1
Q
z
q
m
e
-
j
2
π
q
m
k
/
N
.Denote the number of nonzero values in X
a
(
k
) as X
a
0. The DFT of signal z
(
n
) is(21)
Z
k
=
DFT
z
n
=
∑
m
=
1
Q
z
q
m
e
-
j
2
π
q
m
k
/
N
.Denote the number of nonzero values in Z
(
k
) by N
Z
=
Z
0. The aim of minimization of X
a
0 is to produce the smallest possible value X
a
0
=
s. If this is possible in trivial case z
(
n
)
=
0 only, then our solution is unique. If there exists a nontrivial solution for z
(
n
) with X
a
0
=
s, then we have two different solutions x
(
n
) and x
(
n
)
+
z
(
n
) with the same sparsity s meaning that our solution is not unique.The DFT of signalz
(
n
) can be written in a matrix form as(22)
1
1
⋯
1
e
-
j
2
π
q
1
/
N
e
-
j
2
π
q
2
/
N
⋯
e
-
j
2
π
q
Q
/
N
⋯
⋯
⋯
⋯
e
-
j
2
π
q
1
N
-
1
/
N
e
-
j
2
π
q
2
N
-
1
/
N
⋯
e
-
j
2
π
q
Q
N
-
1
/
N
z
q
1
z
q
2
⋯
z
q
Q
=
Z
0
Z
1
⋯
Z
N
-
1
.Since we look for zeros inZ
(
k
), without loss of generality, we can rewrite system (22) in the form normalized with the first column corresponding to q
1 as(23)
1
1
⋯
1
1
e
-
j
2
π
q
12
/
N
⋯
e
-
j
2
π
q
1
Q
/
N
⋯
⋯
⋯
⋯
1
e
-
j
2
π
q
12
N
-
1
/
N
⋯
e
-
j
2
π
q
1
Q
N
-
1
/
N
z
q
1
z
q
2
⋯
z
q
Q
=
Z
0
Z
1
e
j
2
π
q
1
/
N
⋯
Z
N
-
1
e
j
2
π
q
1
N
-
1
/
N
,where(24)
q
1
n
=
q
n
-
q
1
.In general, during the minimization, we haveQ variables z
(
q
m
) (Q degrees of freedom). First assume that there is no common period (smaller than N) in columns of the transform matrix for the missing sample positions q
i. This case corresponds to pairwise coprime numbers q
12
,
q
13
,
…
,
q
1
Q. Then Q variables z
(
q
m
) can be used to produce Q
-
1 zeros in Z
(
k
) at the positions where there is no signal and, in the worst possible case, to cancel out all s nonzero coefficients in X
(
k
). Therefore the largest possible number of zero values in X
(
k
)
+
Z
(
k
) is (
Q
-
1
)
+
s. The lowest possible number of nonzero values in X
(
k
)
+
Z
(
k
) is N
-
(
Q
-
1
)
-
s. If(25)
N
-
Q
-
1
-
s
>
s
,then the considered solution is unique since only the trivial solution z
(
n
)
=
0 results in sparsity s and every nontrivial solution results in X
a
0
>
s. If we obtain the reconstructed signal with sparsity(26)
s
≥
N
-
Q
+
1
2
,then the solution is not unique. However, if 2
s
<
N
-
Q
+
1, then it still does not mean that the solution is unique since we assumed that there is no periodicity in transform matrix (23). Next we will include all possible cases when some of the columns of transform matrix in (23) may have a common period lower than N.The matrix of coefficientsZ
(
k
) cannot be periodic with period smaller than Q. Thus, with regard to the period of the whole matrix, the worst case would be the transformation matrix which repeats after exactly Q rows, where Q is divisor of N. Denote the number of repetitions by R
=
N
/
Q.For periodic structure of transformation matrix in (23), with such a period that the rows are repeated R times within N, the largest number of zero values in Z
(
k
) is now R
(
Q
-
1
). In addition, the nonzero values in Z
(
k
), in the worst possible case, can cancel all s nonzero DFT values of X
(
k
). Thus, in this case, the lowest possible number of nonzero values in X
(
k
)
+
Z
(
k
) is N
-
R
(
Q
-
1
)
-
s. For the unique solution it should be greater than the signal sparsity; that is, N
-
R
(
Q
-
1
)
-
s
>
s or N
/
(
2
Q
)
>
s. This is the result of the uncertainty principle in the DFT, presented in Section 3.2.The process does not end here. In the minimization process, we must also consider all subsets of missing samplesq
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}. Namely, it can happen that the worst case regarding the maximal number of zero values in Z
(
k
) is not the case with the full set of variables z
(
q
). It could happen that some subsets of the variables q
m
∈
N
Q may produce a higher number of zero values in Z
(
k
) than the whole set of variables. It means that the reconstruction algorithm may find some variables z
(
q
i
) to be zero valued and vary only a subset of remaining variables z
(
q
i
).Subsets of Missing Samples. We have concluded that the periodicity R reduces the sparsity of X
(
k
)
+
Z
(
k
), by increasing the number of possible zero values in Z
(
k
). Consider a general set of missing sample positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}. Then the algorithm for uniqueness should check periods for all possible subsets of missing samples. Assuming as in Theorem 1, without loss of generality, that N
=
2
r the cases are as follows.(1) Using all missing samples, assuming that there is no common period for all of them (in the sense of (23)), the unique solution is obtained if s
<
N
-
(
Q
-
1
)
-
s. The cases with periodic matrix structure will be included in the steps that follows.(2) Consider minimal possible number of periodsR
>
1 for N
=
2
r. It is R
=
2 repetitions in the matrix of coefficients (23) with period N
/
2. Any subset of N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} containing only even or only odd positions can be considered as a set of minimization variables with period N
/
2. The number of missing samples q
m
∈
N
Q at even positions can be written as(27)
N
E
=
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
0
.The same should be done for odd positions in q
m
∈
N
Q:(28)
N
O
=
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
1
.Since we look for the worst case in our reconstruction algorithm, we choose the set with more variables (more degrees of freedom). It is(29)
Q
2
=
max
b
=
0,1
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
=
b
.Since the number of periods in matrix of coefficients is 2 for these two subsets of missing samples, it means that at most(30)
2
Q
2
-
1zero values can be produced in Z
(
k
). It can be larger than (
Q
-
1
). Therefore beside the condition s
<
N
-
(
Q
-
1
)
-
s considered in step (1) we have also to check(31)
s
<
N
-
2
Q
2
-
1
-
sand use the worst case as the limit for s. It means that, at this point, we should compare Q and 2
Q
2
-
1.Note that the largest possibleQ
2 is Q
2
=
N
/
2. In this case, the solution is unique if(32)
2
s
<
N
-
N
+
1
=
1
.This corresponds to the case when all even (or all odd) signal samples are missing. Then we cannot uniquely reconstruct a signal even for sparsity s
=
1.(3) This analysis should be continued for all possible periods inN. For N
=
2
r the next possible period is N
/
4 with the number of periods R
=
4. Coefficients in the matrix (23) are periodic with N
/
4 if the distance between missing samples is four. Thus, we should divide the set of all missing sample positions N
Q into subsets where distances between q
i are multiples of 4, that is, when mod
⁡
(
q
i
,
4
) is a constant. There are 4 such subsets obtained for mod
⁡
(
q
i
,
4
)
=
b, where b
=
0,1
,
2,3. In the same way as in step (2), denote the cardinality of the largest subset by Q
4:(33)
Q
4
=
max
b
=
0,1
,
2,3
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
4
=
b
.If we find Q
4 such that(34)
4
Q
4
-
1
>
2
Q
2
-
1
,
4
Q
4
-
1
>
Q
-
1
,then it means that in z
(
n
) we can consider as variables (nonzero values) only the samples from the set containing q
i such that mod
⁡
(
q
i
,
4
)
=
b producing Q
4. Then the unique solution is obtained only if(35)
s
<
N
-
4
Q
4
-
1
-
s
.The worst case is when the positions of all missing samples are such that Q
4
=
N
/
4. Then the solution is unique if s
<
2. In the worst case with as many as 3
N
/
4 of available samples (Q
=
Q
4
=
N
/
4) we may reconstruct only signals with sparsity s
=
1.(4) Next possible period forN
=
2
r is N
/
8. The periodicity with period 8 should be considered for any subset of q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} calculating(36)
Q
8
=
max
b
=
0,1
,
2,3
,
4,5
,
6,7
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
8
=
b
.If(37)
8
Q
8
-
1
>
max
⁡
Q
-
1
,
2
Q
2
-
1
,
4
Q
4
-
1
,then the sparsity further reduces to(38)
s
<
N
-
8
Q
8
-
1
-
s
.The worst case when the positions of all missing samples are such that Q
8
=
N
/
8 the solution is unique for s
<
4. In this case even with 7
N
/
8 of available samples we may reconstruct only the signals with sparsity s
=
1,2
,
3.(5) The process should continue for all possible periods2
h
<
N, h
=
4,5
,
…
,
r
-
1. We should calculate(39)
Q
2
h
=
max
b
=
0,1
,
…
,
2
h
-
1
⁡
card
⁡
q
:
q
∈
N
Q
,
mod
⁡
q
,
2
h
=
b
.If it is such that(40)
2
h
Q
2
h
-
1
>
max
⁡
Q
-
1
,
2
Q
2
-
1
,
4
Q
4
-
1
,
…
,
2
h
-
1
Q
2
h
-
1
-
1
,then the sparsity constraint for uniqueness is(41)
s
<
N
-
2
h
Q
2
h
-
1
-
s
.(6) Summing up all the cases we get the theorem result that the uniqueness condition is(42)
s
<
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
s
.In the final stage if just two special samples(43)
q
i
∈
N
Q
,
q
i
+
N
/
2
∈
N
Qare missing, then Q
2
r
-
1
-
1
=
1 with the solution being nonunique if(44)
s
≥
N
-
N
2
-
s
.Thus special positions of two missing samples reduce the maximal number of components that can uniquely be detected to N
/
4
-
1.(7) This kind of proof can be generalized for any signal lengthN with possible periods of matrix obtained as divisors of N.


## 3.2. Uncertainty Principle and Theorem1 Bounds

The bounds for sparsity are compared with the results following from the uncertainty relation for the DFT(45)
Q
·
N
Q
≥
N
,where the number of nonzero values in z
(
q
) is denoted by Q and the number of the nonzero values in its DFT Z
(
k
) is N
Q. In the worst case, for a given Q and for the worst possible distribution of positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}, we have(46)
N
Q
=
N
Q
.Consider first the case when we cannot exclude the possibility that the signal DFT assumes values related to the missing sample positions and the worst possible distribution of positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}. The maximal number of nonzero values is N
Q. In the worst case s of nonzero signal DFT values can cancel s nonzero values in Z
(
k
) meaning that the minimal number of nonzero values, in the worst case, is N
Q
-
s. Since it should not be the solution of our minimization problem, the case with all z
(
q
), producing the signal and its sparsity should be lower: N
Q
-
s
>
s or(47)
s
<
N
Q
2
=
N
2
Q
.For arbitrary signal whose values cannot be described by the missing sample positions and for the worst possible distribution of positions we getN
Q
-
1
>
s or(48)
s
<
N
-
Q
Q
=
N
Q
-
1
.These two cases are obtained through the previous analysis as the special worst cases of Theorem1 and Corollary 2 as well.


## 3.3. Proof of Corollary2

In Theorem1 we assumed that Z
(
k
) takes the maximal possible number of Q
-
1 zero values and that at the same time the remaining nonzero values of Z
(
k
) cancel out all signal components X
(
k
). This assumption is very unlikely since after we assumed the maximal possible number of Q
-
1 zeros in Z
(
k
), we have only one remaining degree of freedom. It means that we can cancel out one signal component with one remaining variable and we assume that all other components have specific values so that they will also be canceled out. Consider now the case when signal components are not adjusted to these fixed values of Z
(
k
). Then, in reality, we can expect to cancel out only one component in X
(
k
) with one variable. Repeating Theorem 1 proof with(49)
s
≥
N
-
2
h
Q
2
h
-
1
-
1for nonuniqueness instead of s
<
N
-
2
h
Q
2
h
-
1
-
s for uniqueness produces the proof of Corollary 2.


## 3.4. Proof of Theorem3

Here we will start with two missing samplesq
m
1 and q
m
2 at the distance q
m
1
-
q
m
2
=
N
/
2
=
2
r
-
1
=
2
h. The worst case is Q
2
h
-
1
=
1 with the uniqueness condition(50)
s
<
N
-
N
2
-
1
=
N
2
-
1
.These special positions of two missing samples reduce the maximal number of components that can uniquely be detected to s
=
N
/
2
-
2. However in this case the positions of nonzero DFT values k
0
i
∈
K
s
=
{
k
01
,
k
02
,
…
,
k
0
s
} should be very specific. All of them should be on either even or odd positions, producing(51)
S
2
r
-
h
=
S
2
1
=
min
b
=
0,1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
=
b
=
min
⁡
0,2
=
0
.If that is not the case, then(52)
S
2
1
=
min
b
=
0,1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
=
b
=
min
⁡
1,1
=
1
>
0will reduce the count of zero values that can be achieved in the worst case in X
(
k
)
+
Z
(
k
). Since S
2 of the signal nonzero coefficients are not at the positions of nonzero values of Z
(
k
) then, in the best possible case, only (
s
-
S
2
) out of s nonzero values of the DFT can be canceled out by the predetermined missing sample values (as in Theorem 1). In addition to N
-
2
r
-
1
Q
2
r
-
1
-
1
-
(
s
-
S
2
) nonzero values of X
(
k
)
+
Z
(
k
) at the nonzero positions of Z
(
k
), there are S
2 nonzero values of X
(
k
) positioned at the zero-value positions of Z
(
k
). They cannot be canceled by Z
(
k
). The uniqueness condition for h
=
r
-
1 will therefore require (53)
s
<
N
-
2
r
-
1
Q
2
r
-
1
-
1
-
s
-
S
2
1
+
S
2
1
s
<
N
-
2
h
Q
2
h
-
1
-
s
-
S
2
r
-
h
+
S
2
r
-
h
.This correction of the uniqueness condition with S
2
1 should be done only if Q
2
h
=
Q
N
/
2
=
Q
2
r
-
1
=
2. Denote by P
h
(
l
) the sorted array(54)
P
h
l
=
sort
b
=
0,1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
r
-
h
=
b
.The correction S
2
1
=
S
2
r
-
h with h
=
r
-
1 can be calculated as(55)
S
2
r
-
h
=
∑
l
=
1
Q
2
h
-
1
P
h
l
.For Q
2
h
=
Q
2
r
-
1
=
Q
N
/
2
=
1 (when there are no two samples at the distance N
/
2) the upper summation limit will be 0 and this kind of correction will not be done; S
2
1
=
0. Note that the sum of all P
h
(
l
), l
=
1,2
,
…
,
2
r
-
h is equal to the signal sparsity s.In the same way, forh
=
r
-
2 (missing samples at a distance being multiple of N
/
4) the period of Z
(
k
) is 4. In the worst case when Q
N
/
4
=
Q
2
r
-
2
=
4, the maximal number of nonzero values in X
(
k
) at a distance being multiple of 4 can be canceled out (with nonzero values of Z
(
k
)). The remaining nonzero values in the DFT of signal will be on the zero positions of Z
(
k
) and cannot be canceled out. Note that if Q
N
/
4
=
Q
2
r
-
2
=
3, then two nonzero values in Z
(
k
) will remain (with 3 variables we can make only 2 zero values in each period of Z
(
k
)). The total number of the nonzero values of X
(
k
) that can be canceled is the sum of the two largest numbers in P
h
(
l
) defined by P
h
(
4
)
+
P
h
(
3
)
=
s
-
P
h
(
1
)
-
P
h
(
2
), where(56)
P
h
l
=
sort
b
=
0,1
,
2,3
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
4
=
b
.The number of remaining nonzero DFT values that cannot be canceled out is(57)
S
2
2
=
P
h
1
+
P
h
2
=
∑
l
=
1
Q
2
r
-
2
-
1
P
h
l
.Note that if Q
2
h
=
Q
N
/
4
=
Q
2
r
-
2
=
2, then three nonzero values exist in one period of Z
(
k
) (only one zero value of Z
(
k
) can be obtained within a period) meaning that the total number of signal values that can be canceled out is P
h
(
4
)
+
P
h
(
3
)
+
P
h
(
2
)
=
s
-
P
h
(
1
). The number of remaining nonzero values of X
(
k
) is S
2
2
=
P
h
(
1
)
=
∑
l
=
1
Q
2
r
-
2
-
1
‍
P
h
(
l
).The uniqueness condition is that(58)
s
<
N
-
2
h
Q
2
h
-
1
-
s
-
S
2
r
-
h
+
S
2
r
-
hwith (59)
P
h
l
=
sort
b
=
0,1
,
2
,
…
,
2
r
-
h
-
1
⁡
card
⁡
k
:
k
∈
K
s
,
mod
⁡
k
,
2
r
-
h
=
b
S
2
r
-
h
=
∑
l
=
1
Q
2
h
-
1
P
h
l
,and 2
r
-
h
=
4 for h
=
r
-
2. The same analysis is done for all h, using (58)-(59). The value of s satisfying (58) for all h produces Theorem 3 statement.


## 3.5. Proof of Corollary4

This corollary follows from Theorem3 neglecting the probability that several DFT coefficients can be canceled out by predetermined values of the missing samples. Then instead of (
s
-
S
2
r
-
h
) in (58) we have just one sample and(60)
s
≥
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
1
+
S
2
r
-
his used for nonuniqueness instead of the uniqueness condition(61)
s
<
N
-
max
h
=
0,1
,
…
,
r
-
1
⁡
2
h
Q
2
h
-
1
-
s
-
S
2
r
-
h
+
S
2
r
-
h
.


## 4. The Worst Case Signal Form

For the worst case, defined by Theorem1, the set of possible amplitudes and phases of signal components is related to the missing sample positions. For the missing sample positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} used in the minimization process, the worst case in the minimization process is when the period of the transformation matrix is such that it repeats immediately after Q samples, in the sense described in the proof of Theorem 1. Then the minimal number of nonzero values in DFT Z
(
k
) is N
Q
=
N
/
Q. It means that Q variables z
(
q
1
)
,
z
(
q
2
)
,
…
,
z
(
q
Q
) can be determined such that Q
-
1 values of Z
(
k
) within k
=
0,1
,
2
,
…
,
Q
-
1 are zero-valued and only one Z
(
k
) is nonzero. In the worst case, this scenario repeats immediately after Q values (it repeats N
/
Q times). The maximal number of zero values in Z
(
k
) is then (
Q
-
1
)
N
/
Q. The number od nonzero values (sparsity) in Z
(
k
) is N
/
Q.Now we will investigate the form of the signal DFT so that the Theorem1 sparsity bound holds with equality sign. The worst case assumes existence of the maximal number of zeros in Z
(
k
) and one nonzero value of Z
(
k
) in each period N
/
Q. It also assumes that all s signal components can be canceled out by this nonzero value of Z
(
k
) and corresponding periodic nonzero values Z
(
k
+
i
Q
). The maximal number of zeros in Z
(
k
) within one period defines values of all nonzero values of variables z
(
n
) in the time domain (with a possibility to cancel out one signal component in X
(
k
)
+
Z
(
k
) within the considered period).Let us consider subsets ofQ equations defined by (22). The first subset will be written for frequencies k
=
0,1
,
2
,
…
,
Q
-
1, the second for k
=
Q
,
Q
+
1
,
…
,
2
Q
-
1, and so on until the last one for k
=
N
-
Q
,
N
-
Q
+
1
,
…
,
N
-
1. Assume the signal DFT coefficient X
(
k
0
i
) (the one that we want to use along with Q
-
1 zero values of Z
(
k
) to calculate variables z
(
q
1
)
,
z
(
q
2
)
,
…
,
z
(
q
Q
)) is within the subset of equations for k
=
i
Q
,
i
Q
+
1
,
…
,
i
Q
+
Q
-
1. Then the solution of(62)
e
-
j
2
π
q
1
i
Q
/
N
e
-
j
2
π
q
2
i
Q
/
N
⋯
e
-
j
2
π
q
Q
i
Q
/
N
e
-
j
2
π
q
1
i
Q
+
1
/
N
e
-
j
2
π
q
2
i
Q
+
1
/
N
⋯
e
-
j
2
π
q
Q
i
Q
+
1
/
N
⋯
⋯
⋯
⋯
e
-
j
2
π
q
1
k
0
i
/
N
e
-
j
2
π
q
2
k
0
i
/
N
⋯
e
-
j
2
π
q
Q
k
0
i
/
N
⋯
⋯
⋯
⋯
e
-
j
2
π
q
1
i
Q
+
Q
-
1
/
N
e
-
j
2
π
q
2
i
Q
+
Q
-
1
/
N
⋯
e
-
j
2
π
q
Q
i
Q
+
Q
-
1
/
N
z
q
1
z
q
2
⋯
z
q
Q
=
0
0
⋯
-
X
k
0
i
⋯
0will produce maximal sparsity for this frequency range; that is, Z
(
k
)
+
X
(
k
)
=
0 for all considered frequencies k
=
i
Q
,
i
Q
+
1
,
…
,
i
Q
+
Q
-
1. Solution for the missing sample values is(63)
z
q
1
z
q
2
⋯
z
q
Q
=
e
-
j
2
π
q
1
i
Q
/
N
e
-
j
2
π
q
2
i
Q
/
N
⋯
e
-
j
2
π
q
Q
i
Q
/
N
e
-
j
2
π
q
1
i
Q
+
1
/
N
e
-
j
2
π
q
2
i
Q
+
1
/
N
⋯
e
-
j
2
π
q
Q
i
Q
+
1
/
N
⋯
⋯
⋯
⋯
e
-
j
2
π
q
1
k
0
i
/
N
e
-
j
2
π
q
2
k
0
i
/
N
⋯
e
-
j
2
π
q
Q
k
0
i
/
N
⋯
⋯
⋯
⋯
e
-
j
2
π
q
1
i
Q
+
Q
-
1
/
N
e
-
j
2
π
q
2
i
Q
+
Q
-
1
/
N
⋯
e
-
j
2
π
q
Q
i
Q
+
Q
-
1
/
N
-
1
0
0
⋯
-
X
k
0
i
⋯
0
.Values of z
(
q
), obtained from this system, do not change for other s
-
1 nonzero signal DFT values X
(
k
0
m
), k
0
m
≠
k
0
i. With the previous system of equations and its solution for missing samples z
(
q
) we have used all degrees of freedom of Q-dimensional variable z
(
q
). More zero values in the DFT of the resulting signal X
(
k
)
+
Z
(
k
) (lower sparsity of this signal) can be obtained only if the remaining signal DFT values X
(
k
0
m
), k
0
m
≠
k
0
i are canceled out, by chance. In the worst case, assumed by Theorem 1, all remaining s
-
1 nonzero DFT coefficients k
0
m
≠
k
0
i should be canceled out, with the already determined missing sample values z
(
q
). Since the transformation matrix is periodic, this will happen only if all remaining signal DFT coefficients assume very specific positions k
0
m
=
k
0
i
+
r
m
Q and specific values(64)
X
k
0
m
e
j
2
π
q
1
k
0
m
/
N
=
X
k
0
i
e
j
2
π
q
1
k
0
i
/
N
X
k
0
m
=
e
-
j
2
π
k
0
m
-
k
0
i
Q
q
1
/
N
X
k
0
i
X
k
0
m
=
e
-
j
2
π
r
m
Q
q
1
/
N
X
k
0
i
,since the periodicity is established with respect to q
1.For a given set of missing sample positionsq
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
} probability that all components of a measured signal assume specific positions with specific amplitudes and phases (related to the missing sample positions) defined by (64) are a zero-probability event.


### 4.1. Group Delay and Missing Sample Positions

Consider a signaly
(
n
), periodic with period N
/
Q and defined for n
=
0,1
,
…
,
N
/
Q
-
1 as(65)
y
n
=
δ
n
-
n
0
X
k
0
i
,where n
0 is the reminder after q
1 is divided by N
/
Q. Note that the worst case requires that all missing sample positions q
m are at the positions being multiple of N
/
Q. It means that the reminder after division of q
m by N
/
Q is a constant denoted by n
0. The DFT of the considered signal is(66)
Y
k
=
e
-
j
2
π
n
0
k
/
N
/
Q
X
k
0
i
k
=
0,1
,
…
,
N
Q
-
1
.It is interesting to note that the signal DFT valuesX
(
k
0
m
), defined with (64), are obtained as a subset of s values from {
Y
(
k
)
∣
k
=
0,1
,
…
,
N
/
Q
-
1
}; that is,(67)
X
k
0
m
∈
e
-
j
2
π
n
0
k
/
N
/
Q
X
k
0
i
∣
k
=
0,1
,
…
,
N
Q
-
1
.In the worst case, the DFT values of signal should bes samples of a full DFT of a periodic signal which would have group delay coinciding with the missing sample positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}, since q
m
=
q
n
+
l
(
N
/
Q
) in this case. It means that if the missing samples produce a periodic structure, then the signal values should follow this structure as well.Example. For the signal with N
=
32 and missing samples at(68)
q
m
∈
N
Q
=
2,3
,
8,13,19,22,23,28,30the limit for sparsity s (when we claim that the reconstructed sparse signal is unique, assuming that all signal amplitudes may be related to the missing sample positions) is s
<
8. In this example, we will show what properties a signal must satisfy in the limit case s
=
8 so that the solution is not unique. To simplify the notation assume that one DFT value of reconstructed signal is X
(
5
)
=
2.The limit of sparsitys
=
8 is obtained in the first example with Q
16
=
2 and 16
(
2
-
1
)
=
16. As explained, it corresponds to the missing sample positions q
2
=
3 and q
5
=
q
2
+
N
/
2. It means that the missing sample values of other samples z
(
q
m
) will be adjusted to their correct zero positions and only z
(
q
2
)
=
z
(
3
)
=
z
3 and z
(
q
5
)
=
z
(
19
)
=
z
19 will assume nonzero values. In this case the set of missing samples variables reduces to q
m
∈
N
Q
=
{
3,19
} with Q
=
Q
16
=
2. The DFT Z
(
k
) of such a signal is equal to (69)
Z
k
=
z
3
e
-
j
2
π
3
k
/
32
+
z
19
e
-
j
2
π
19
k
/
32
=
e
-
j
2
π
3
k
/
32
z
3
+
-
1
k
z
19
k
=
0,1
,
…
,
31
.In the worst case Z
(
k
) should have maximal possible number of zeros. We conclude that either z
3
=
z
19 or z
3
=
-
z
19 should hold; otherwise the sparsity of Z
(
k
) would be 32. In addition, Z
(
k
) should cancel out all signal components including assumed X
(
5
)
=
2. Since z
3
=
z
19 would produce Z
(
2
k
+
1
)
=
0 it would not be able to cancel X
(
5
). Therefore we must use z
3
=
-
z
19 with(70)
Z
5
=
e
-
j
2
π
15
/
32
z
3
-
z
19
=
-
X
5
=
-
2
.It means that z
3
=
-
z
19
=
-
e
j
2
π
15
/
32 and(71)
Z
k
=
-
2
e
-
j
2
π
3
k
-
15
/
32
for odd
k
0
for even
k
.In order to cancel all nonzero values ofX
(
k
) they must be located at odd positions (where Z
(
k
) is nonzero)(72)
5
,
k
02
,
k
03
,
k
04
,
k
05
,
k
06
,
k
07
,
k
08and must be of opposite sign and equal amplitude to the corresponding (determined) values of Z
(
k
):(73)
X
k
0
i
=
-
Z
k
0
i
=
2
e
-
j
2
π
3
k
0
i
-
15
/
32
for
i
=
2,3
,
…
,
8resulting in(74)
X
k
=
2
e
-
j
2
π
3
k
-
15
/
32
for
k
∈
5
,
k
02
,
k
03
,
k
04
,
k
05
,
k
06
,
k
07
,
k
08
0
elsewhere
.In this case sparsity ofX
(
k
)
+
Z
(
k
) is 8, the same as the sparsity of the X
(
k
). Two solutions of our minimization problem are signal x
(
n
)
=
I
D
F
T
[
X
(
k
)
] and x
(
n
)
+
z
(
n
) where(75)
z
n
=
IDFT
Z
k
=
δ
n
-
3
-
δ
n
-
19
.Both of these signals have the same sparsity s
=
8 and satisfy the same set of available samples.However, if sampled signalx
(
n
) is not the signal of very specific form (74), then the solution of sparsity s
=
8 will be unique for a given set of available samples. Then z
(
n
)
=
δ
(
n
-
3
)
-
δ
(
n
-
19
) will not be in position to cancel all 8 DFT values of signal and the sparsity of X
(
k
)
+
Z
(
k
) will be 8 only for z
(
n
)
=
0, producing unique solution.SignalY
(
k
)
=
-
Z
(
2
k
-
1
) is Y
(
k
)
=
2
e
-
j
2
π
(
3
(
2
k
-
1
)
-
15
)
/
32
=
2
e
-
j
2
π
(
3
k
-
9
)
/
16. It is periodic with period N
/
Q
=
16. Group delay of this signal is n
0
=
3 with period 16. Therefore within n
=
0,1
,
…
,
31 group delays n
0
=
3 and n
0
+
16
=
19 of Y
(
k
) correspond to the missing sample positions. The signal must have the form X
(
k
0
m
)
∈
{
2
e
-
j
2
π
(
3
k
-
9
)
/
16
∣
k
=
0,1
,
…
,
N
/
Q
-
1
}, with k
=
3 corresponding to k
0
m
=
2
k
-
1
=
5 producing X
(
5
)
=
2.


## 4.1. Group Delay and Missing Sample Positions

Consider a signaly
(
n
), periodic with period N
/
Q and defined for n
=
0,1
,
…
,
N
/
Q
-
1 as(65)
y
n
=
δ
n
-
n
0
X
k
0
i
,where n
0 is the reminder after q
1 is divided by N
/
Q. Note that the worst case requires that all missing sample positions q
m are at the positions being multiple of N
/
Q. It means that the reminder after division of q
m by N
/
Q is a constant denoted by n
0. The DFT of the considered signal is(66)
Y
k
=
e
-
j
2
π
n
0
k
/
N
/
Q
X
k
0
i
k
=
0,1
,
…
,
N
Q
-
1
.It is interesting to note that the signal DFT valuesX
(
k
0
m
), defined with (64), are obtained as a subset of s values from {
Y
(
k
)
∣
k
=
0,1
,
…
,
N
/
Q
-
1
}; that is,(67)
X
k
0
m
∈
e
-
j
2
π
n
0
k
/
N
/
Q
X
k
0
i
∣
k
=
0,1
,
…
,
N
Q
-
1
.In the worst case, the DFT values of signal should bes samples of a full DFT of a periodic signal which would have group delay coinciding with the missing sample positions q
m
∈
N
Q
=
{
q
1
,
q
2
,
…
,
q
Q
}, since q
m
=
q
n
+
l
(
N
/
Q
) in this case. It means that if the missing samples produce a periodic structure, then the signal values should follow this structure as well.Example. For the signal with N
=
32 and missing samples at(68)
q
m
∈
N
Q
=
2,3
,
8,13,19,22,23,28,30the limit for sparsity s (when we claim that the reconstructed sparse signal is unique, assuming that all signal amplitudes may be related to the missing sample positions) is s
<
8. In this example, we will show what properties a signal must satisfy in the limit case s
=
8 so that the solution is not unique. To simplify the notation assume that one DFT value of reconstructed signal is X
(
5
)
=
2.The limit of sparsitys
=
8 is obtained in the first example with Q
16
=
2 and 16
(
2
-
1
)
=
16. As explained, it corresponds to the missing sample positions q
2
=
3 and q
5
=
q
2
+
N
/
2. It means that the missing sample values of other samples z
(
q
m
) will be adjusted to their correct zero positions and only z
(
q
2
)
=
z
(
3
)
=
z
3 and z
(
q
5
)
=
z
(
19
)
=
z
19 will assume nonzero values. In this case the set of missing samples variables reduces to q
m
∈
N
Q
=
{
3,19
} with Q
=
Q
16
=
2. The DFT Z
(
k
) of such a signal is equal to (69)
Z
k
=
z
3
e
-
j
2
π
3
k
/
32
+
z
19
e
-
j
2
π
19
k
/
32
=
e
-
j
2
π
3
k
/
32
z
3
+
-
1
k
z
19
k
=
0,1
,
…
,
31
.In the worst case Z
(
k
) should have maximal possible number of zeros. We conclude that either z
3
=
z
19 or z
3
=
-
z
19 should hold; otherwise the sparsity of Z
(
k
) would be 32. In addition, Z
(
k
) should cancel out all signal components including assumed X
(
5
)
=
2. Since z
3
=
z
19 would produce Z
(
2
k
+
1
)
=
0 it would not be able to cancel X
(
5
). Therefore we must use z
3
=
-
z
19 with(70)
Z
5
=
e
-
j
2
π
15
/
32
z
3
-
z
19
=
-
X
5
=
-
2
.It means that z
3
=
-
z
19
=
-
e
j
2
π
15
/
32 and(71)
Z
k
=
-
2
e
-
j
2
π
3
k
-
15
/
32
for odd
k
0
for even
k
.In order to cancel all nonzero values ofX
(
k
) they must be located at odd positions (where Z
(
k
) is nonzero)(72)
5
,
k
02
,
k
03
,
k
04
,
k
05
,
k
06
,
k
07
,
k
08and must be of opposite sign and equal amplitude to the corresponding (determined) values of Z
(
k
):(73)
X
k
0
i
=
-
Z
k
0
i
=
2
e
-
j
2
π
3
k
0
i
-
15
/
32
for
i
=
2,3
,
…
,
8resulting in(74)
X
k
=
2
e
-
j
2
π
3
k
-
15
/
32
for
k
∈
5
,
k
02
,
k
03
,
k
04
,
k
05
,
k
06
,
k
07
,
k
08
0
elsewhere
.In this case sparsity ofX
(
k
)
+
Z
(
k
) is 8, the same as the sparsity of the X
(
k
). Two solutions of our minimization problem are signal x
(
n
)
=
I
D
F
T
[
X
(
k
)
] and x
(
n
)
+
z
(
n
) where(75)
z
n
=
IDFT
Z
k
=
δ
n
-
3
-
δ
n
-
19
.Both of these signals have the same sparsity s
=
8 and satisfy the same set of available samples.However, if sampled signalx
(
n
) is not the signal of very specific form (74), then the solution of sparsity s
=
8 will be unique for a given set of available samples. Then z
(
n
)
=
δ
(
n
-
3
)
-
δ
(
n
-
19
) will not be in position to cancel all 8 DFT values of signal and the sparsity of X
(
k
)
+
Z
(
k
) will be 8 only for z
(
n
)
=
0, producing unique solution.SignalY
(
k
)
=
-
Z
(
2
k
-
1
) is Y
(
k
)
=
2
e
-
j
2
π
(
3
(
2
k
-
1
)
-
15
)
/
32
=
2
e
-
j
2
π
(
3
k
-
9
)
/
16. It is periodic with period N
/
Q
=
16. Group delay of this signal is n
0
=
3 with period 16. Therefore within n
=
0,1
,
…
,
31 group delays n
0
=
3 and n
0
+
16
=
19 of Y
(
k
) correspond to the missing sample positions. The signal must have the form X
(
k
0
m
)
∈
{
2
e
-
j
2
π
(
3
k
-
9
)
/
16
∣
k
=
0,1
,
…
,
N
/
Q
-
1
}, with k
=
3 corresponding to k
0
m
=
2
k
-
1
=
5 producing X
(
5
)
=
2.


## 5. Conclusion

Reconstruction of a sparse signal, using recently proposed gradient-based method, is done by considering missing samples as variables. Theorems for the uniqueness of the solution obtained by varying missing samples, in the case of an arbitrary and already reconstructed signal, are stated and proved. The calculation complexity of the proposed theorems is low. The theory is illustrated on numerical and statistical examples.The proposed approach can be extended to other signal transforms including nonredundant basis (dictionaries). One of the possible redundant basis closely related to the presented DFT is short time Fourier transform with overlapping windows [17, 18].



---

*Source: 629759-2015-12-27.xml*