arXiv:1706.05201v1 [cs.IT] 16 Jun 2017

THE MONTENEGRIN ACADEMY OF SCIENCES AND ARTS
PROCEEDINGS OF THE SECTION OF NATURAL SCIENCES, 22, 2017.

Conditions for Unique Reconstruction of Sparse
Signals Using Compressive Sensing Methods
Ljubiša Stanković, Miloš Daković, Srdjan Stanković, Irena Orović

Abstract
A signal is sparse in one of its representation domain if the number of nonzero coefficients in that domain is much smaller than the total number of coefficients. Sparse signals can be reconstructed from a
very reduced set of measurements/observations. The topic of this paper are conditions for the unique reconstruction of sparse signals from
reduced set of observations. After the basic definitions are introduced,
the unique reconstruction conditions are reviewed using the spark, restricted isometry, and coherence of the measurement matrix. Uniqueness of the reconstruction of signals sparse in the discrete Fourier domain (DFT), as the most important signal transformation domain, is
considered as well.

1

Introduction

A discrete-time signal can be transformed into other domains using different
signal transformations. Some signals that cover the whole considered interval in one domain could be sparse in a transformation domain, i.e., could
be located within a few nonzero coefficients. An observation or measurement is a linear combination of sparsity domain coefficients. Since the signal
samples are linear combinations of the signal transformation coefficients they
could be considered as the observations of a sparse signal in the transformation domain. Compressive sensing is a field dealing with a model for data
acquisition including the problem of sparse signal recovery from a reduced
set of observations [1–13]. A reduced set of observations can be a result of a
desire to sense a sparse signal with the lowest possible number of measurements/observations (compressive sensing). It can also be a result of a physical or measurement unavailability to take a complete set of observations [3].
The authors are with the University of Montenegro, 81000 Podgorica, Montenegro.

Conditions for Unique Reconstruction

2

In applications it could happen that some arbitrarily positioned samples of a
signal are so heavily corrupted by disturbances that it is better to omit them
and consider as unavailable in the analysis and to try to reconstruct the signal
with a reduced set of samples [14–16]. Although the reduced set of observations/samples appears in the first case as a result of user strategy to compress
the information, while in the next two cases the reduced set of samples is not
a result of user intention, all of them can be considered within the unified
framework. Under some conditions, a full reconstruction of a sparse signal
can be performed with a reduced set of observations/samples, as in the case
if a complete set of samples/observations were available [4, 17–20]. A priori information about the nature of the analyzed signal, i.e., its sparsity in
a known transformation domain, must be used in this analysis. Sparsity is
the main requirement that should be satisfied in order to efficiently apply the
compressive sensing methods for sparse signal reconstruction.
Compressive sensing methods are successfully applied to many fields,
including radar signal processing [21–26], time-frequency analysis [21,27–29],
L-statistics [16, 30], data hiding [31], communications [32], image processing
[33, 34], etc.
Topic of this paper are conditions for the unique reconstruction of sparse
signals from reduced set of observations/samples. The basic idea for unique
reconstruction will be introduced through an illustrative and simple example in the next section. Then the unique reconstruction condition will be
explained within the spark, restricted isometry, and coherence framework.
A special case of the signals sparse in the discrete Fourier domain (DFT), as
the most important signal transformation domain, will be considered at the
end. A simple uniqueness criterion will be presented and illustrated on an
example.

2

Illustrative Examples

Consider a large set of N numbers X (0), X (1),...,X ( N − 1). Assume that only
one of them is nonzero. We do not know either its position or its value. The
aim is to find the position and the value of this number. This case can be
related to many real life examples when we have to find one sample which
differs from other N − 1 samples. The problem can easily be reformulated to
the case when only one number differs from the expected and known value,
and all other assume their expected-known values.
The nonzero value at an position i will be denoted by X (i ). A direct way
to find the position i of nonzero sample would be to perform up to N mea-

2

3

ILLUSTRATIVE EXAMPLES

surements and compare each X (m) with zero. However, if N is very large
and there is only one nonzero sample we can get the result with just a few
observations/measurements. A procedure for the reduced number of observations/measurements is described next.
Take random numbers as weighting coefficients ai , i = 0, 1, 2, ..., N − 1,
for each coefficient. Measure the total value of all N weighted coefficients,
with weights ai . Since only one of them is different from the known expected
values mi (or from zero) we will get the total measured value
G = a1 m1 + a2 m2 + ... + ai (mi + X (i )) + ... + a N m N .
Next we will subtract the expected value GT = a1 m1 + a2 m2 + ... + a N m N
from G. The obtained observation/measurement, denoted by y(0), is
N −1

y ( 0 ) = G − GT =

∑

a k X ( k ) = a i X ( i ),

k =0

since the nonzero value in the space of X (0), X (1),...,X ( N − 1) is at one position only, X (k ) = X (i )δ(k − i ), k = 0, 1, . . . , N − 1.
As an illustration consider a set of N bags with coins. Assume that only
one bag contains false coins of a weight mi + X (i ). It is different from the
known weights mi of true coins in bag i. The goal is to find the position and
the difference in weight of false coins. From each of N bags we will take
ai , i = 1, 2, ...N, coins, respectively. Number of coins taken from the ith bag
is denoted by ai . The total measured weight of all coins from N bags is M,
Fig.1.
After the expected value is subtracted the observation/measurement y(0)
is obtained
N −1

y (0) =

∑

X (k )ψk (0),

(1)

k =0

where the weighting coefficients for this measurement are denoted by ψk (0) =
ak , k = 0, 1, ..., N − 1. In the space of unknowns (variables) X (0), X (1),...,X ( N −
1) this equation represents an N-dimensional hyperplane. We know that only
one unknown X (k) is nonzero at an unknown position k = i. The intersection of hyperplane (1) with any of the coordinate axes could be a solution
of our problem.
Assuming that a single X (k ) is nonzero, a solution will exist for any k.
Thus, one measurement would produce a set of N possible single nonzero
values equal to
X (k ) = y(0)/ψk (0),

ψk (0) 6= 0, k = 0, 1, 2, ..., N − 1.

Conditions for Unique Reconstruction

4

1

2

a1

N

3

a2

a3

aN

+

G−GT= a1 m1+a2 m2+...+ai (mi+X(i))+...+aN mN
−(a1 m1 +a2 m2 +...+ai mi+...+aN mN) = ai X(i)
i=?, X(i)=?

Figure 1: There are N bags with coins. One of them, at an unknown position, contains false coins. False coins differ from the true ones in mass for
unknown X (i ) = ∆m. The mass of the true coins in the ith bag is mi .

As expected, from one measurement we are not able to solve the problem and
to find the position and the value of nonzero sample.
For N = 3 possible solutions are illustrated with circles in Fig.2a), denoting intersections of measurements hyperplane with coordinate axes.
If we perform one more measurement y(1), with another set of weighting coefficients ψk (1), k = 0, 1, ..., N − 1, and get measured value y(1) =
X (i )ψi (1) the result will be a hyperplane
N −1

y (1) =

∑

X (k)ψk (1).

k =0

This measurement will produce a new set of possible solutions for each X (k )
defined by
X (k ) = y(1)/ψk (0), k = 0, 1, 2, ..., N − 1.
If these two hyperplanes (sets of solutions) produce only one common value
X (i ) = y(0)/ψi (0) = y(1)/ψi (1).

2

5

ILLUSTRATIVE EXAMPLES

Figure 2: The solution illustration for N = 3, K = 1, and various possible
cases: (a) Three possible solutions for one measurement plane. (b) Unique
solution for two measurement planes. (c) Two possible solutions for two
measurement planes.

then it is the solution of our problem.
In a matrix form these two measurements can be written as

X (0)

 

y (0)
ψ0 (0) ψ1 (0) ... ψN −1 (0) 
X (1)

=

y (1)
ψ0 (1) ψ1 (1) ... ψN −1 (1)
...
X ( N − 1)






y = AX
where A is the matrix of coefficients (measurement matrix)


ψ0 (0) ψ1 (0) ... ψN −1 (0)
A=
ψ0 (1) ψ1 (1) ... ψN −1 (1)
and y are observations/measurements of sparse variable X.
Common value for two measurements X (i ) = y(0)/ψi (0) and X (i ) =
y(1)/ψi (1) is unique if
ψi (0)ψk (1) − ψi (1)ψk (0) 6= 0
for any i 6= k.
In order to prove this statement assume that two different solutions X (i )
and X (k ), for the case of one nonzero coefficient, satisfy the same measurement hyperplane equations
ψi (0) X (i ) = y(0), ψi (1) X (i ) = y(1)

Conditions for Unique Reconstruction

6

and
ψk (0) X (k ) = y(0),

ψk (1) X (k ) = y(1).

Then
ψi (0) X (i ) = ψk (0) X (k )
and
ψi (1) X (i ) = ψk (1) X (k ).
If we divide these two equations we get
ψi (0)/ψi (1) = ψk (0)/ψk (1)
or ψi (0)ψk (1) − ψi (1)ψk (0) = 0. This is contrary to the assumption that
ψi (0)ψk (1) − ψi (1)ψk (0) 6= 0.
The same conclusion can be made considering matrix form relations for
X (i ) and X (k ). If both of them may satisfy the same two measurements then




y (0)
y (1)



y (0)
y (1)





ψi (0) ψk (0)
ψi (1) ψk (1)



X (i )
0





ψi (0) ψk (0)
ψi (1) ψk (1)



0
X (k)



=

=

.

(2)

Subtraction of the previous matrix equations results in


ψi (0) ψk (0)
ψi (1) ψk (1)



X (i )
− X (k)



= 0.

For ψi (0)ψk (1) − ψi (1)ψk (0) 6= 0 follows X (i ) = X (k ) = 0. Therefore two
different nonzero solutions X (i ) and X (k) in this case cannot exist. This concludes the proof that the solution is unique if

ψi (0)ψk (1) − ψi (1)ψk (0) = det

ψi (0) ψk (0)
ψi (1) ψk (1)



6= 0

for any i 6= k. It also means that rank (A2 ) = 2 for any A2 being a 2 × 2
submatrix of the matrix of coefficients (measurement matrix) A.
Let us consider M measurements in this example. Since we have assumed
that only one coefficient X (i ) is nonzero it will satisfy all measurements
ψi (0) X (i ) = y(0), ψi (1) X (i ) = y(1), . . . , ψi ( M − 1) X (i ) = y( M − 1).

2

7

ILLUSTRATIVE EXAMPLES

The solution will not be unique if there is another coefficient X (k ), k 6= i
satisfying
ψk (0) X (k) = y(0), ψk (1) X (k ) = y(1), . . . , ψk ( M − 1) X (k ) = y( M − 1).
Then the corresponding coefficients of the measurement matrix satisfy
ψi (0)
ψ (1)
ψ ( M − 1)
= i
= ... = i
.
ψk (0)
ψk (1)
ψk ( M − 1)
In this case measurement matrix is

ψ0 (0)
ψ1 (0)

ψ
(
1
)
ψ1 (1)
0

A =
..
..

.
.
ψ0 ( M − 1) ψ1 ( M − 1)

...
...
..
.

ψ N −1 (0 )
ψ N −1 (1 )
..
.

...

ψ N −1 ( M − 1 )







The solution is not unique if any two columns are linearly dependent. The
uniqueness requires that all two column submatrices A2 of A are of rank 2.
The determinant for all A2T A2 is nonzero.
In numerical and practical applications we would not be satisfied, if for
example det(A2T A2 ) 6= 0 but det(A2T A2 ) = ε close to zero. In this case the theoretical condition for a unique solution would be satisfied, however the analysis and possible inversion would be highly sensitive to any kind of noise,
including quantization noise. Thus, a practical requirement is that the determinant is not just different from zero, but that it sufficiently differs from zero
so that an inversion stability and robustness to a noise is achieved. Inversion stability for a matrix B = A2T A2 is commonly described by the condition
number of matrix
λmax
cond {B} =
λmin
where λmax and λmin are the largest and the smallest eigenvalue of matrix
B. The inversion stability worsens as λmin approaches to zero (when λmin is
small as compared to λmax ). For stable and robust calculations a requirement
λmax
≤ 1+δ
λmin
is imposed, with a nonnegative constant δ being sufficiently small. In our
example this condition should hold for all submatrices A2 .

Conditions for Unique Reconstruction

8

As a next example consider a signal described by a weighted sum of K
harmonics from a set of possible oscillatory functions e j2πkn/N , k = 0, 1, 2,
..., N − 1,
x (n) = A1 e j2πk1 n/N + A2 e j2πk2 n/N + ... + AK e j2πkK n/N ,
with K  N. In the DFT domain this signal will be sparse with X (k ) =
DFT { x (n)} having only few nonzero values at k = k i , i = 1, 2, ..., K. According to the sampling theorem the sampling of this kind of signals should
be adjusted to the maximal expected signal frequency k = max{k1 , k2 , ..., k K }.
For an arbitrary set of frequencies, it means that we should adjust sampling to
the maximal possible frequency k = N − 1 and to use the full set of N signal
values/measurements at n = 0, 1, 2, ..., N − 1 in order to avoid aliasing.
However, if we know that the signal consists of only K  N functions
with unknown amplitudes, then regardless of their frequencies, the signal
can be fully reconstructed from a reduced set of samples. Samples can be
considered as weighted measurements of the sparse function X (k ),
N −1

y (0) = x ( n1 ) =

∑

X (k )ψk (n1 ),

k =0

with the weighting coefficients ψk (n1 ) = exp( j2πn1 k/N )/N. The previous
relation is the IDFT. Now a similar analysis like in the previous illustrative
example can be performed, assuming for example K = 1 or K = 2. We
can find the position and the value of nonzero X (k ) using just a few signal
samples y(i ).
This model corresponds to many signals in real life. For example, in the
Doppler-radar systems the speed of a radar target is transformed into a frequency of a sinusoidal signal [23, 24]. Since the returned signal contains only
one or just a few targets, the signal representing target velocity is a sparse
signal in the DFT domain. It can be reconstructed from fewer samples than
the total number of radar return signal samples N, Fig.3.
In signal processing the DFT as the domain of signal sparsity is commonly
used, since it plays the central role in engineering applications [3, 20]. Note
that in the compressive sensing theory random measurement matrices are
mainly used. The compressive sensing results and algorithms are used as a
tool to solve the problems involving sparse signals.

3

9

DEFINITIONS

60 X(k)

2 x(n)

Two target velocities
within 64 bins range

1

40

0
20

−1

0

Target velocities transformed
into a dense signal

−2
0

20

40

60 (a)

2 y(n)

0

60 Y(k)

1

20

40

60 (b)

DFT of y(n)
before reconstruction

40

0
20

−1

0

Mesurements of x(n)

−2
0

20

40

60 (c)

0

20

40

60 (d)

Figure 3: (a) Signal in the frequency domain, where it is sparse (for example, velocities of two targets in Doppler radar signal). (b) Signal in the time
domain, where it is dense. (c) Reduced set of measurements (samples) and
(d) its DFT before reconstruction, calculated using the available samples only.
Real parts of signals are presented.

3

Definitions

A big set of discrete-time data x (n), n = 0, 1, . . . , N − 1, with a large number
of samples N is considered. Its coefficients in a transformation domain are
denoted as
X = [ X (0), X (1), ..., X ( N − 1)] T ,
where T represents the transpose operation. We consider a signal to be sparse
in this transformation domain if the number of nonzero coefficients K is much
smaller than the number of the original signal samples N, i.e., if X (k) = 0 for
k ∈
/ K = {k1 , k2 , ..., k K } and K  N. The number of nonzero coefficients is
commonly denoted by kXk0

kXk0 = card {K} = K,
where card {K} is the cardinality of set K. It is equal to the number of elements in K. It is called the `0 -norm (norm-zero) or the `0 -pseudo-norm of
vector X although it does not satisfy the norm properties.

Conditions for Unique Reconstruction

10

The observations/measurements are defined as linear combinations of
signal coefficients in the sparsity domain
N −1

y(m) =

∑

X (k )ψk (m),

(3)

k =0

where m = 0, 1, . . . , M − 1 is the measurement index and ψk (m) are the
weighting coefficients. The vector form of the measurement signal is denoted
by y
y = [y(0), y(1), ..., y( M − 1)] T .
The measurements defined by Eq.(3) can be written as a undetermined
system of M < N equations


y (0)
y (1)
..
.










ψ0 (0)
ψ0 (1)
..
.

 
 
=
 

y ( M − 1)

ψ1 (0)
ψ1 (1)
..
.

···
···
..
.

ψ0 ( M − 1) ψ1 ( M − 1) · · ·

ψ N −1 (0 )
ψ N −1 (1 )
..
.







ψ N −1 ( M − 1 )



X (0)
X (1)
..
.






X ( N − 1)

or using matrix notation
y = AX
where A is the measurement matrix of size M × N.
The fact that the signal is sparse with X (k ) = 0 for k ∈
/ K = {k1 , k2 , ..., k K }
is not included in the measurement matrix A since the positions of the nonzero
values are unknown. If the knowledge that X (k ) = 0 for k ∈
/ K were included
then a reduced system would be obtained as






y (0)
y (1)
..
.
y ( M − 1)





 
 
=
 

ψk1 (0)
ψk1 (1)
..
.

ψk2 (0)
ψk2 (1)
..
.

···
···
..
.

ψk1 ( M − 1) ψk2 ( M − 1) · · ·

ψkK (0)
ψkK (1)
..
.
ψkK ( M − 1)




X (k1 )
  X (k2 ) 


  .. 
 . 
X (k K )

with a reduced M × K measurement matrix AK defined as
y = AK XK .

(4)

This is an overdetermined system of equation, K < N. Matrix AK would
be formed if we assumed/knew the positions of nonzero samples k ∈ K.
It would follow from the measurement matrix A by omitting the columns
corresponding to the zero-valued coefficients in X.

3

11

DEFINITIONS

3.1

Common Measurement Matrices

Some common measurement matrices used in practical applications and theoretical considerations will be presented here.
Randomness of measurement matrices is a favorable property in compressive sensing and matrices with random elements are often used. The
most common is the measurement matrix with zero-mean unity variance
Gaussian distributed numbers as elements
1
φk (n) ∼ √ N (0, 1)
M

√
normalized with 1/ M so that the energy of each column is one.
In signal processing the most common transform is the DFT. The coefficients of its direct transform matrix Φ are defined as
φk (n) = exp(− j2πnk/N ).
The inverse DFT matrix coefficients are ψk (n) = N1 exp( j2πnk/N ). Commonly the measurements are the signal samples y(m − 1) = x (nm ) for m =
1, . . . , M where
nm ∈ M = {n1 , n2 , . . . , n M } ⊂ {0, 1, . . . , N − 1},
and
y ( m − 1) = x ( n m ) =

1
N

N −1

∑

X (k )e j2πnm k/N .

k =0

Therefore, the measurement matrix is obtained by keeping the rows of the
inverse DFT matrix corresponding to the samples at nm ∈ {0, 1, . . . , N − 1},
for the measurements m = 1, 2, . . . , M,


e j2πn1 /N
e j2πn2 /N
..
.

···
···
..
.

1 e j2πn M /N

···

1

1 1
A=
.
N  ..


e j2πn1 ( N −1)/N
e j2πn2 ( N −1)/N 

.
..

.

(5)

e j2πn M ( N −1)/N

This is a partial inverse DFT matrix. In compressive sensing theory it is common to normalize the measurement matrix so that the energy of its columns
(diagonal elements of AH√
A matrix) is equal to one. Then the factor 1/N in A
should be replaced by 1/ M.

12

Conditions for Unique Reconstruction

In order to increase randomness in the Fourier transform matrix, the measurements may be taken at any random instant. Then the measurement vector elements are y(m − 1) = x (tm ) where tm , m = 1, 2, . . . , M are random
instants within the considered time interval T. The measurement matrix follows then from the Fourier series definition x (t) = ∑kN=−01 X (k ) exp( j2πkt/T ).
It has been assumed that the Fourier series coefficients are within 0 ≤ k ≤
N − 1. The measurements matrix is


1 e j2πt1 /T · · · e j2πt1 ( N −1)/T
1 e j2πt2 /T · · · e j2πt2 ( N −1)/T 


(6)
A = .

..
..
..
 ..

.
.
.

1 e j2πt M /T · · · e j2πt M ( N −1)/T
√
with a possible normalization factor 1/ M. This measurement matrix is a
partial random inverse Fourier transform matrix.

4

Reconstruction Problem Formulation

The signal can be reconstructed from its measurements defined by vector y by
finding the sparsest vector X that corresponds to the measurements y. Hence,
by introducing the notation for the number of components based on the `0 norm K = kXk0 , the fundamental minimization problem can be formulated
as:
min kXk0 subject to y = AX.
(7)
In general, the `0 -norm is not very suitable for most minimization methods. However, a class of algorithms is based on the minimization of the number of coefficients K = kXk0 in an implicit way. For instance, in certain applications we can predict the number of components or we are able to estimate
the position of non-zero coefficients. Thus, compared to the direct search
method, the computational complexity will be significantly reduced if we are
able to estimate positions of nonzero coefficients and solve the problem with
the minimal possible number of nonzero coefficients. The important class of
this algorithms are matching pursuit (MP) algorithms.
Minimization of the number of non-zero coefficients using the `0 -norm
is a nonconvex optmization problem that cannot be solved using well developed iterative algorithms and linear programming methods [35–42]. To
avoid dealing with NP-hard problems, significant efforts have been undertaken to replace the nonconvex and discontinuous `0 -norm with a convex
and continuous norm that would be more appropriate for optimization. As

4

RECONSTRUCTION PROBLEM FORMULATION

13

a result, the `1 -norm (norm-one) has been commonly employed in many signal reconstruction approaches [43–46]. It has been shown that, under certain
conditions, minimization of the `1 -norm produces the same solution as the
minimization of the `0 -norm.
In the `1 -norm based reconstructions the problem is formulated as
min kXk1

subject to y = AX

where

N −1

k X k1 =

∑

| X (k)| .

k =0

This is the so-called basis pursuit (BP) approach to sparse signal reconstruction.

4.1
4.1.1

Conditions for Unique Reconstruction
Spark

The spark of a matrix A is defined as the smallest number of linearly dependent columns of A. In other words if spark{A} = K, then any collection of
K1 < K columns of A are linearly independent.
Spark can also be defined as a minimal number of nonzero entries in a
vector X 6= 0 such that AX = 0
min kXk0

such that AX = 0

If matrix A is of size N × K with N > K and spark{A} = K + 1 then all
K × K submatrices of matrix A are nonsingular, i.e., with nonzero determinant.
The analysis of a signal with an arbitrary sparsity K is similar to the analysis for K = 1. To get the first set of possible solutions for K nonzero coefficients (of sparsity K) we need K measurements. For any combination of K
(out of N) nonzero coefficients X (k ), k ∈ {k1 , k2 , ..., k K }, we will get a possible
solution. There exist ( N
K ) such possible combinations/solutions. Additional K
measurements will be used to produce another set of ( N
K ) possible solutions.
The intersection of these two sets is then the solution of our problem.
Consider the case when the number of measurements M is twice higher than the
sparsity K, M = 2K. The K-sparse solution is unique if the determinants of all A2K
submatrices of matrix A are different from zero.
This statement will be proven by contradiction. Assume that M = 2K
measurements are available within the vector y. Assume that two different

Conditions for Unique Reconstruction

14

solutions for X of sparsity K exist. Denote the nonzero parts of the solutions
(1)
(2)
by XK and XK . Both of them satisfy the measurements equation,
(1) (1)

AK XK = y
and

(2) (2)

AK XK = y,
(1)

(2)

where AK and AK are two different submatrices of matrix A of size M × K
(1)

(2)

corresponding to the elements in XK and XK . If we rewrite these equations
by adding zeros
"
#
"
#
i 0
i (1)
h
h
K
XK
(2)
(1)
(2)
(1)
(8)
=y
and
AK AK
AK AK
(2) = y
XK
0K
and subtract them we get
h

(1)
AK

(2)
AK

i

"

(1)

#
(1)
XK
(2) = 0.
−XK

(9)

(2)

There are
i solutions for XK and XK if the determinant of matrix
h no nonzero

A2K = A(K1) A(K2) is nonzero. If all possible submatrices A2K (including
all lower order submatrices) of measurement matrix A are nonsingular then
two solutions of sparsity K cannot exist, and the solution is unique. Note that
N
there are (2K
) submatrices A2K .
Based on the previous analysis, the solution for a K sparse problem is
unique if
spark{A} > 2K.
h
i
(1)
(2)
For M > 2K the matrix A2K = AK AK dimension is M × 2K. Again

T A ) = 2K system (9) does not have a nonzero soluif rank(A2K ) = rank(A2K
2K
T A ) =
tion. It means that the reconstruction is unique. If rank(A2K ) = rank(A2K
2K
2K for all submatrices A2K then spark{A} > 2K.
If the vector X is of sparsity K, with kXk0 = K then if

K<

1
spark {A}
2

the solution X is unique.
In order to prove this statement (that has been already explained) consider a measurement matrix A whose spark is spark {A}. Then for a sparse

4

RECONSTRUCTION PROBLEM FORMULATION

15

vector X of sparsity K = spark {A} obviously there exists such a combination
of nonzero elements in X so that they coincide with the dependent columns.
Then we can obtain
AX = 0.
This property is used for the spark definition as well.
Note that for any X of sparsity K < spark {A} the relation AX = 0 will
not hold, since corresponding independent columns of A multiplied with
nonzero elements of X cannot produce a zero result. Since K < spark {A} it
means that all sets of K columns from A are independent.
The proof of the previous statement will be based on the contradiction.
Assume that X is a solution of AX = y and that its sparsity satisfies K <
1
2 spark { A }. Assume also that there is another solution H such that AH = y
and H is also sparse with sparsity lower than 12 spark {A}. Since
AH = AX = y
A(H − X) = 0
then
spark {A} < kH − Xk0
or
spark {A} < kH − Xk0 ≤ kHk0 + kXk0
spark {A} − kHk0 ≤ kXk0 .
The inequality follows from the fact that two nonzero elements, at the same
position in H and X, can produce a zero element in H − X, while two zero elements in these vectors cannot produce a nonzero element in H − X. If there is
another solution H such that kHk0 < 12 spark {A} then from the last inequality follows that kXk0 > 12 spark {A} . This is a contradiction to the assumption
that both solutions H and X have sparsity lower than 12 spark {A}.
4.1.2

Restricted Isometry Property

Note that for any square matrix its determinant is equal to the product of its
eigenvalues
T
det{A2K
A2K } = λ1 λ2 · . . . · λ2K .
T A
The condition that the solution is unique if the determinant of A2K
2K for all
A2K submatrices of matrix A are different from zero can be rewritten as

min |λi | > 0.
i

Conditions for Unique Reconstruction

16

In numerical and practical applications we would not be satisfied, if any
of the determinants is very close to zero. In this case the theoretical condition
for a unique solution would be satisfied, however the analysis and possible
inversion would be highly sensitive to any kind of noise in measurements.
Thus, a practical requirement is that the determinant is not just different from
zero, but that it sufficiently differs from zero so that an inversion stability and
noise robustness is achieved.
From the matrix theory it is known that the norm of a matrix A2K satisfies
λmin ≤

T AT A X
X2K
kA2K X2K k22
2K 2K 2K
=
≤ λmax ,
2
T
X
kX2K k2
2K X2K

(10)

where λmin and λmax are the minimal and the maximal eigenvalue of the ma2
T A
2
2
trix A2K
2K and k X k2 = | X (0)| + . . . | X ( N − 1)| is the squared `2 -norm
(norm-two).
The isometry property for a linear transformation matrix A holds if

kAXk22 = kXk22 or

kAXk22
= 1.
kXk22

The restricted isometry property (RIP) for a matrix A2K and a 2K-sparse
vector X2K holds if
1 − δ2K ≤

kA2K X2K k22
≤ 1 + δ2K ,
kX2K k22

(11)

where 0 ≤ δ2K < 1 is the isometric constant. From Eqs.(10) and (11) we can
write
δ2K = max{1 − λmin , λmax − 1}.
Commonly, isometric constant is defined by λmax − 1 and it is calculated
T A
as maximal eigenvalue of matrix A2K
2K − I. Normalized energies of the
T A ) are assumed. Othercolumns of matrix A (diagonal elements of A2K
2K
wise, the normalization factors should be added. For complex-valued matriH A .
ces Hermitian transpose should be used in A2K
2K
For a K-sparse vector X and a measurement matrix A the RIP is satisfied if
relation (11) holds for all submatrices AK with 0 ≤ δK < 1. The solution for
K-sparse vector is unique if the measurement matrix satisfy the RIP for 2K-sparse
vector X with 0 ≤ δ2K < 1.
Note that if the RIP is satisfied then λmin > 0. It means that there is no
H A
A2K submatrix of A such that A2K
2K is a singular matrix. The uniqueness
proof reduces to the previous one.

4

17

RECONSTRUCTION PROBLEM FORMULATION

Restricted isometry property for small δ2K is closer to the isometry property and improves the solution stability. It can be related to the matrix condiT A
tional number. The conditional number of a matrix A2K
2K is defined as the
ratio of its maximal and minimal eigenvalues
n
o
λmax
T
cond A2K
A2K =
.
λmin
If a matrix A2K satisfies the restricted isometry property with δ2K then
n
o
1 + δ2K
T
cond A2K
A2K ≤
.
1 − δ2K
With small values of δ2K the conditional number is close to one, meaning
stable invertibility and low sensitivity to the input noise (small variations of
the input signal (measurements) do not cause large variations of the result).
Common requirement for this constant is
√
0 ≤ δ2K < 2 − 1.
The restricted isometry constant within this range will also guarantee the
equivalence of the solutions obtained in the reconstruction based on the `0 norm and the `1 -norm minimization [17, 18].
4.1.3

Coherence

The mutual coherence (coherence index) of a matrix A is defined as the maximal absolute value of the normalized scalar product of its two columns
µ = max |µmk | , for m 6= k
where
µmk = q

−1
∗
∑iM
=0 α m ( i ) α k ( i )
2

−1
M −1
∑iM
=0 | αm (i )| ∑i =0 | αk (i )|

2

(12)

2
−1
and αk (i ) are the elements of the kth column of matrix A. If ∑iM
=0 | αk (i )| =
2
−1
∑iM
=0 | αm (i )| then
1
∗
∑ M−
0 αm (i ) αk (i )
µmk = i=M
.
(13)
2
1
∑i=−
0 | αk (i )|

Note that µmk , m 6= k, are the off-diagonal elements of matrix A H A normalized with the corresponding diagonal elements.

Conditions for Unique Reconstruction

18

This index plays an important role in the analysis of measurement matrices. The coherence index should be as small as possible, or in other words the
incoherence is a desirable property. With smaller values of coherence index
the matrix A H A is closer to the identity matrix.
The condition that all eigenvalues of matrix A H A are nonzero can be written in terms of the coherence index. In general, the eigenvalue relation for
matrix A H A reads
(A H A)u = λu
where u denotes an eigenvector. For an eigenvector we can always choose
that its maximal coordinate is um = maxk (uk ) = 1 and uk ≤ 1 for k 6= m.
Now we can write the general eigenvalue relation in the form

∑ µmk uk = λum = λ
k

or

∑

µmk uk = λ − µmm

k,k 6=m

From this relation we can conclude

|λ − µmm | ≤

∑

|µmk uk | ≤

k,k 6=m

∑

|µmk |.

k,k 6=m

Considering eigenvalue λ as a variable and µmk as constants we conclude
that the last inequality describes a disc area with the center at µmm and radius
∑k,k6=m |µmk |. It does not include point λ = 0 if
µmm >

∑

|µmk |.

(14)

k,k 6=m

Therefore the matrix A H A will be nonsingular if the above condition is met.
This is the Gershgorin circle (disk) theorem.
For normalized matrix A H A we have µmm = 1 and
µ = max |µmk | .
m6=k

We have already concluded that the solution for K-sparse vector will be
H A
unique if for all possible submatrices A2K the matrices A2K
2K are nonsinH
gular. Note that the off-diagonal elements of A2K A2K are a subset of the offdiagonal elements of matrix A H A. The same holds for the diagonal elements.
It mean that the coherence µ of matrix A will be always greater than or equal
to the coherence of any submatrix A2K .

4

19

RECONSTRUCTION PROBLEM FORMULATION

H A , and unique solution for
The nonsingularity condition for all matrices A2K
2K
a K sparse vector X, is achieved if

1 > (2K − 1)µ
or
K<

1
1
(1 + ).
2
µ

The proof follows from (14) for normalized matrix A H A. The inequality
2K

1 = µmm >

∑

|µmk |

k=1,k 6=m

is satisfied if 1 > (2K − 1)µ since ∑2K
k =1,k 6=m | µmk | < (2K − 1) µ.
The coherence index cannot be arbitrarily small for an M × N matrix A
(M < N). The Welch upper bound relation holds
s
N−M
.
(15)
µ≥
M ( N − 1)
The Gershgorin circle (disk) theorem can be used to determine the spark
lower bound. If the relation K < (1 + 1/µ)/2 holds for a given K then it
H A
holds for any order lower than K. It means that all submatrices A2K
2K of
2K and lower order are nonsingular. Therefore the spark of such a matrix is
greater than 2K
spark(A) > 2K
(16)
or
K<

1
spark(A)
2

if K < (1 + 1/µ)/2. It means that
spark(A) ≥ 1 +

4.2

1
.
µ

Numerical Example

Consider 5 × 8 measurement matrix

0.1
0.1
0.3 −0.7
0.7
 0.4 −0.8 −0.4 −0.1
0.3

0.3
0.5
−
0.5
0.4
0.5
A=

 −0.7 −0.3
0.1
0.3
0.4
−0.5
0.1 −0.7 −0.5 −0.1

−0.1
0.1
0.3
0.3
−0.7
0.1
−0.5
0.5
−0.4 −0.8

0.3
−0.5
−0.4
−0.7
−0.1




.



(17)

Conditions for Unique Reconstruction

20

Columns of this matrix are normalized. The norm of each column is equal
to one. The matrix dimensions are small so we can solve NP-hard problems
and calculate the spark and the restricted isometry property constants, by
checking all possible combinations, in a reasonable time.
4.2.1

Spark Calculation

For the spark calculation we first concluded that there is no all zero column,
meaning that spark{A} > 1. Then we have check linear dependence of each
pairs of columns. In total (82) combinations are checked by calculating rank
of each 2 × 5 submatrix. In all cases rank was equal to 2 meaning that all
pair of two columns are linearly independent. It means that spark{A} > 2.
Next all (83) possible combinations of three columns are considered. For all
submatrices we concluded that their rank is 3 meaning that there is no a set
of three linearly dependent columns in the measurement matrix A. Therefore spark{A} > 3. Calculation is repeated for all combinations of four and
five columns with the same result. The final conclusion is that the spark of
this matrix is spark{A} = 6 meaning that all combinations of five and less
columns are linearly independent. The uniqueness condition based on matrix
spark state that sparsity K limit is
K<

1
spark{A} = 3.
2

According to the spark based uniqueness condition, the reconstruction is
unique for K = 1 and K = 2. We may conclude that if we find a sparse
vector X in the reconstruction with sparsity K ≤ 2 then this is the sparsiest
possible solution of our problem.
4.2.2

Coherence Calculation

Coherence of the considered matrix is calculated a maximal absolute value of
the off-diagonal element of A T A. If the diagonal elements were not normalized then this maximal value should be normalized with the diagonal values
of this matrix. For the considered measurement matrix A we get
µ = 0.49
resulting in the sparsity limit
K<

1
1
(1 + ) ≈ 1.5204.
2
µ

4

RECONSTRUCTION PROBLEM FORMULATION

21

The worst case, that determine value of µ, was coherence between 5th and
7th column of the considered matrix. The reconstruction is unique only for
K = 1. Note that in contrast to the spark limit this condition will guarantee
that the same unique solution is obtained using `1 -norm and `0 -norm. This is
the reason why this limit is more conservative.
For a measurement matrix of order 5 × 8 the smallest possible value of the
the coherence index is
s
r
N−M
3
µ≥
=
= 0.2928
M ( N − 1)
5×7
with maximal possible bound K < 2.2078. The matrix with minimal coherence index is quite specific and it is called the equiangular tight frame (ETF).
In practice many optimization approaches are based on finding the measurement matrix with coherence as low as possible (as close to the ETF as possible).
4.2.3

Restricted Isometry Property Constant Calculation

Restricted isometry property (RIP) constants of orders 1, 2, 3, 4, and 5 are
calculated. For the calculation of the RIP constant with assumed sparsity
K = 1 all possible submatrices A1 are formed. These are 5 × 1 matrices.
There are 8 of them. The matrices A1T A1 are formed. All of them are scalars
equal to 1 with λ = 1, resulting in
δ1 = max{1 − λmin , λmax − 1} = 0.
Next the sparsity K = 2 of the resulting X is assumed. All possible measurement submatrices A2 corresponding to this sparsity are formed. There
are (82) of them. The matrices A2T A2 are formed. Then their eigenvalues are
calculated. The RIP constant δ2 is obtained as a maximal value of
δ2 = max{1 − λmin , λmax − 1} = 0.49.
over all possible submatrices A2 .
The calculation is repeated for assumed sparsity K = 3, 4, 5 by forming
corresponding submatrices A3 , A4 , and A5 , respectively. The obtained numerical values for these sparsities are
δ3 = 0.9406
δ4 = 1.2063
δ5 = 1.3368

22

Conditions for Unique Reconstruction

We can conclude that matrix A satisfy the restricted isometry property
0 ≤ δK < 1
for sparsity 1, 2, and 3. The uniqueness condition require that for sparsity
K measurement matrix satisfies restricted isometry property for 2K meaning
that the uniqueness is guarantied only for K = 1. For K = 2 the condition
should be satisfied for δ4 , what is not the case.
The minimization for K sparse vector X √
using `1 -norm will produce the
same result as if `0 -norm were used if δ2K < 2 − 1. It means that there is no
guarantee that `1 norm minimization could be used in the reconstruction for
sparsity K = 1. Note that different bounds have been derived in literature
for this equivalence. One of the derived bounds is that δ2K < 0.493. The
considered measurement matrix A would produce a unique solution with `1 norm based minimization, according to this bound since δ2 = 0.49 < 0.493.
From this example we can see that uniqueness conditions produce different limits, and that they are very restrictive.

4.3

Uniqueness of the DFT of Sparse Signals

In general, the reconstructed signal uniqueness is guarantied if the restricted
isometry property is used and checked. However, two problems exist in the
implementation of this approach. For a specific measurement matrix it produces quite conservative bounds. In addition, uniqueness check with the
restricted isometry property requires a combinatorial approach, which is an
NP hard problem.
In some reconstruction methods the missing measurements are considered as the minimization variables. The available measurements/samples
are known and fixed. 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 [20, 48–54]. Then the missing and available
samples/measurements form a complete set of samples/measurements.
The DFT is such a signal sparsity domain. The solution uniqueness is
defined in the sense that the variation of the missing sample values cannot
produce another signal of the same sparsity. In the case when the signal is
already reconstructed then the uniqueness is checked in the sense that there
is no other signal of the same or lower sparsity with the same set of available
samples [20].
Consider a signal x (n) with n ∈ N = {0, 1, 2, ...., N − 1}. Assume that Q
of its samples at the positions qm ∈ NQ = {q1 , q2 , ...., qQ } are missing/omit-

4

RECONSTRUCTION PROBLEM FORMULATION

23

ted. The signal is sparse in the DFT domain, with sparsity K. The reconstruction goal is to get x (n), for all n ∈ N using available samples at n ∈ M =
N\NQ . A new signal of the form
x a (n) = x (n) + z(n)
will be analyzed here. For the available signal positions n ∈ M the value of
z(n) is fixed z(n) = 0, while z(n) may take arbitrary value at the positions of
missing samples n = qm ∈ NQ = {q1 , q2 , ...., qQ }. If x (n) is a K sparse signal
then the DFT of x a (n) is
Xa (k ) = X (k ) + Z (k )
K

= N ∑ Ai δ(k − k0i ) +
i =1

Q

∑

z(qm )e− j2πqm k/N .

m =1

Positions of nonzero values in X (k ) are k0i ∈ K = {k01 , k02 , ...., k0K } with amplitudes X (k0i ) = N Ai . The values of missing samples of x a (n) = x (n) + z(n)
for n ∈ NQ are considered as variables. The goal of 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 a sparsity measure of the signal transform Xa (k ) [3, 47]. Existence of the unique solution of this problem depends on the number of missing samples, their positions, and the signal form.
If a signal with the transform X (k ) of sparsity K is obtained using a reconstruction method, with a set of missing samples, then the reconstruction X (k )
is unique if there is no other signal of the same or lower sparsity that satisfies
the same set of available samples (using the same set of missing samples as
variables).
Consider a signal x (n) that is sparse in the DFT domain with unknown sparsity.
Assume that the signal length is N = 2r samples and that Q samples are missing
at the instants qm ∈ NQ . Assume that the reconstruction is performed and that the
DFT of reconstructed signal is of sparsity K. The reconstruction result is unique if
the inequality
n
o
K< N−

max

h=0,1,...,r −1

2 h ( Q 2h − 1 ) − K

holds. Integers Q2h are calculated as
Q 2h =

max

b=0,1,...,2h −1

{card{q : q ∈ NQ and mod(q, 2h ) = b}}

(18)

For example, consider a signal with N = 25 = 32 and Q = 9 missing
samples at
qm ∈ NQ = {2, 3, 8, 13, 19, 22, 23, 28, 30}.

Conditions for Unique Reconstruction

24

Using the presented we will find the sparsity limit K when we are able to
claim that the reconstructed sparse signal is unique for any signal form.
• For h = 0 we use Q20 = Q and get 20 ( Q20 − 1) − 1 = ( Q − 1) − 1 = 9.
• For h = 1, the number Q21 is the greater value of
card{q : q ∈ NQ and mod(q, 2) = 0} = card{2, 8, 22, 28, 30} = 5
card {q : q ∈ NQ and mod(q, 2) = 1} = card{3, 13, 19, 23} = 4,
i.e., the maximal number of even or odd positions of missing samples.
Thus Q21 = max {5, 4} = 5 with 21 ( Q21 − 1) = 8.
• Next Q22 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 Q22 = max {2, 1, 3, 3} = 3 with
22 ( Q2h − 1) = 8.
• For Q23 the number 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 Q23 is 2 with
23 ( Q23 − 1) = 8.
• Finally we have two samples at distance 16 (samples at the positions
q2 = 3 and q5 = q2 + N/2) producing Q24 = Q16 = 2 with 24 (2 − 1) =
16.
The reconstructed signal of sparsity K is unique if
K< N−

max

h=0,1,2,3,4

n

o
2 h ( Q2h − 1 ) − K

K < 32 − max {9, 8, 8, 8, 16} − K
K < 32 − 16 − K
or
K < 8.
An extended discussion about the DFT uniqueness, within the framework of
the missing samples as variables, can be found in [20].

5

5

CONCLUSION

25

Conclusion

Sparse signals can be reconstructed from a very reduced set of observations,
through compressive sensing. This property has found applications in many
fields. The topic of this paper was to introduce the basic definitions in compressive sensing. The conditions for exact and unique reconstruction of original signals are of crucial importance in theory and applications. These conditions are reviewed and related in this paper.

Appendix
MATLAB R functions for spark calculation (Algorithm 1), restricted isometry
constant calculation (Algorithm 2) and uniqueness test for partial DFT matrix
(Algorithm 4) are provided. Auxiliary function nextcomb used for generation
of all possible columns combinations of the measurement matrix used in Algorithms 1 and 2 is given in Algorithm 3.
Algorithm 1 Measurement matrix spark calculation
1 function s = spark(A)
2 % Matrix spark calculation
3 [M,N] = size(A);
4 s = M+1;
5 for k = 1:M
6
kk = nchoosek(N,k);
7
p = 1:k;
8
for m = 1:kk
9
A1 = A(:,p);
10
if rank(A1) < k
11
s = k; break
12
end
13
p = nextcomb(p,N);
14
end
15
if s < M+1, break, end
16 end

Conditions for Unique Reconstruction

26

Algorithm 2 Restricted isometry constant calculation
1
2
3
4
5
6
7
8
9
10
11
12

function d = RIP_calc(A,K)
% Restricted isometry constant caluclation
[M,N] = size(A);
d = 0;
kk = nchoosek(N,K);
p = 1:K;
for m = 1:kk
A1 = A(:,p);
l = eig(A1’∗A1);
d = max([d, 1−min(l), max(l)−1]);
p = nextcomb(p,N);
end

Algorithm 3 Auxiliary function for generation of all combinations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function p = nextcomb(p,N)
% Generate next combination (in lexicographical order )
% Input: previous combination p and number of elements N
% Output: next combination or []
i = length(p);
K = N;
while i > 0 && p(i) == K
i = i −1;
K = K−1;
end
if i > 0
p(i ) = p(i )+1;
for k = i+1:length(p)
p(k) = p(k−1)+1;
end
else
p = [];
end

REFERENCES

27

Algorithm 4 Sparsity limit for partial DFT measurement matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function Kt = DFT_check(N,Nq)
% Sparsity limit for partial DFT matrix
% Inputs:
% N − total number of samples (must be power of two)
% Nq − set of missing sample positions
r = log2(N);
if r −round(r) ~= 0, error(’N must be power of two’), end
Kt = N;
for h = 0: r −1
p = rem(Nq,2^h);
Q = zeros(1,2^h);
for s = 0:2^h−1
Q(s+1) = sum(p==s);
end
Q2h = max(Q);
if Kt > (N−2^h∗(Q2h−1))/2
Kt = (N−2^h∗(Q2h−1))/2;
end
end

References
[1] D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information
Theory, vol. 52, no. 4, 2006, pp. 1289–1306.
[2] E.J. Candès, M. Wakin, "An Introduction to Compressive Sampling",
IEEE Signal Processing Magazine, vol. 25, no. 2, March 2008, pp. 21-30.
[3] L. Stanković, M. Daković, S. Stanković, and I. Orović, "Sparse Signal
Processing - Introduction ," Wiley Encyclopedia of Electrical and Electronics
Engineering, John Wiley & Sons, 2017.
[4] E. J. Candès, J. Romberg, T. Tao, “Robust uncertainty principles: Exact
signal reconstruction from highly incomplete frequency information,”
IEEE Transactions on Information Theory, vol. 52, no. 2, 2006, pp. 489-509.
[5] Y. C. Eldar, G. Kutyniok, Compressed Sensing: Theory and Applications,
Cambridge University Press, 2012.

28

Conditions for Unique Reconstruction

[6] R. Baraniuk, “Compressive sensing,” IEEE Signal Processing Magazine,
vol. 24, no. 4, 2007, pp. 118–121.
[7] L. Stanković, S. Stanković, M. G. Amin, “Missing Samples Analysis in
Signals for Applications to L-Estimation and Compressive Sensing”, Signal Processing, Elsevier, vol. 94, Jan. 2014, pp. 401–408.
[8] L. Stanković, Digital Signal Processing with Applications: Adaptive Systems,
Time-Frequency Analaysis, Sparse Signal Processing, CreateSpace Independent Publishing Platform, 2015.
[9] S. Stanković, I. Orović, E. Sejdić, Multimedia Signals and Systems: Basic and
Advanced Algorithms for Signal Processing, Springer International Publishing, second edition, 2015.
[10] S. Stanković, L. Stanković, and I. Orović, “A Relationship between the
Robust Statistics Theory and Sparse Compressive Sensed Signals Reconstruction," IET Signal Processing, 2014.
[11] I. Orovic, and S. Stankovic, "Improved Higher Order Robust Distributions based on Compressive Sensing Reconstruction," IET Signal Processing, vol. 8, no. 7, 2014, pp. 738 - 748.
[12] M. Elad, Sparse and Redundant Representations: From Theory to Applications
in Signal and Image Processing, Springer, 2010.
[13] I. Orović, V. Papić, C. Ioana, X. Li, and S. Stanković, “Compressive Sensing in Signal Processing: Algorithms and Transform Domain Formulations," Mathematical Problems in Engineering, 2016.
[14] L. Stankovic, M. Dakovic, S. Vujovic, "Reconstruction of Sparse Signals
in Impulsive Disturbance Environments," Circuits, Systems and Signal
Processing, vol. 2016. pp. 1-28.
[15] I. Stankovic, I. Orovic, M. Dakovic, and S. Stankovic, "Denoising of
Sparse Images in Impulsive Disturbance Environment," Multimedia Tools
and Applications, pp.1-21, 2017.
[16] S. Stankovic, I. Orovic, and M. Amin, "L-statistics based Modification
of Reconstruction Algorithms for Compressive Sensing in the Presence
of Impulse Noise," Signal Processing, vol.93, no.11, November 2013, pp.
2927-2931.

REFERENCES

29

[17] E. J. Candès, "The restricted isometry property and its implications for
compressed sensing", Comptes Rendus Mathematique, Vol.346, Issues 9-10,
May 2008, pp 589-592.
[18] T. Zhang, "Sparse Recovery with Orthogonal Matching Pursuit Under
RIP," IEEE Trans. on Information Theory, 57(9), 2011, pp. 6215-6221.
[19] D. L. Donoho, M. Elad, V. Temlyakov, “Stable recovery of sparse overcomplete representations in the presence of noise,” IEEE Transactions on
Information Theory, vol. 52, 2006, pp. 6–18.
[20] L. Stanković, M. Daković, "On the Uniqueness of the Sparse Signals Reconstruction Based on the Missing Samples Variation Analysis," Mathematical Problems in Engineering, vol. 2015, Article ID 629759, 14 pages,
doi:10.1155/2015/629759
[21] L. Stankovic, M. Dakovic, T. Thayaparan, Time-Frequency Signal Analysis
with Applications, Artech House, Boston, March 2013.
[22] L. Stankovic, "On the ISAR Image Analysis and Recovery with Unavailable or Heavily Corrupted Data," IEEE Transactions on Aerospace and Electronic Systems, Vol.51, no.3, pp.2093-2106, July 2015
[23] S. Costanzo, A. Rocha, M. D. Migliore, "Compressed Sensing: Applications in Radar and Communications", The Scientific World Journal, Volume 2016, Article ID 5407415, 2 pages, Editorial, 2016.
[24] J. Ender, "On compressive sensing applied to radar", Signal Processing,
Volume 90, Issue 5, May 2010, Pages 1402-1414.
[25] L. Stankovic, S. Stankovic, T. Thayaparan, M. Dakovic, and I. Orovic,
"Separation and Reconstruction of the Rigid Body and Micro-Doppler
Signal in ISAR Part II - Statistical Analaysis," IET Radar, Sonar and Navigation, vol.9, no.9, pp.1155-1161, 2015 doi: 10.1049/iet-rsn.2015.0137
[26] L. Stankovic, S. Stankovic, T. Thayaparan, M. Dakovic, and I. Orovic,
"Separation and Reconstruction of the Rigid Body and Micro-Doppler
Signal in ISAR Part I- Theory," IET Radar, Sonar and Navigation, vol.9,
no.9, pp.1147-1154, 2015 doi: 10.1049/iet-rsn.2015.0096
[27] P. Flandrin, P. Borgnat, "Time-Frequency Energy Distributions Meet
Compressed Sensing," IEEE Transactions on Signal Processing, vol.58,
no.6, pp.2974, 2982, June 2010.

30

Conditions for Unique Reconstruction

[28] L. Stankovic, I. Orovic, S. Stankovic, and M. Amin, "Compressive Sensing Based Separation of Non-Stationary and Stationary Signals Overlapping in Time-Frequency," IEEE Transactions on Signal Processing, Vol. 61,
no. 18, pp. 4562 - 4572, Sept. 2013.
[29] I. Orović, S. Stanković, and T. Thayaparan, "Time-Frequency Based Instantaneous Frequency Estimation of Sparse Signals from an Incomplete
Set of Samples," IET Signal Processing, Special issue on Compressive Sensing
and Robust Transforms, 2014.
[30] S. Stankovic, I. Orovic, M. Amin, "L-statistics based Modification of Reconstruction Algorithms for Compressive Sensing in the Presence of Impulse Noise," Signal Processing, vol.93, no.11, November 2013, pp. 29272931 , 2013.
[31] G. Hua, Y. Hiang, G. Bi, "When Compressive Sensing meets Data Hiding", IEEE Signal Processing Letters, Vol. 23, No. 4, April 2016.
[32] J. Bazerque, G. Giannakis, "Distributed spectrum sensing for cognitive
radio networks by exploiting sparsity," IEEE Trans. Signal Process., vol.
58, no. 3, pp. 1847-1862, Mar. 2010.
[33] S. Stanković, and I. Orović, “An Approach to 2D Signals Recovering in
Compressive Sensing Context," Circuits, Systems and Signal Processing,
doi 10.1007/s00034-016-0366-8
[34] I. Stanković, I. Orović, M. Daković, and S. Stanković, "Denoising of
Sparse Images in Impulsive Disturbance Environment," Multimedia Tools
and Applications, 2017, doi:10.1007/s11042-017-4502-7
[35] M. Fornsaier, H. Rauhut, "Iterative thresholding algorithms", Applied and
Computational Harmonic Analysis, vol. 25, no. 2, Sept. 2008, pp. 187- 208.
[36] S. Mallat, Z. Zhang, "Matching pursuits with time-frequency dictionaries", IEEE Transactions on Signal Processing, vol. 41, no. 12. pp. 3397-3415,
1993.
[37] J. A. Tropp, A. C. Gilbert, "Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit," IEEE Transactions on Information Theory, Vol. 53, np. 12, pp. 4655-4666, 2007.
[38] D. Needell, J. A. Tropp, "CoSaMP: Iterative signal recovery from
noisy samples", Applied and Computational Harmonic Analysis, 2008. DOI:
10.1016/j.acha.2008.07.002.

REFERENCES

31

[39] R. Tibshirani, "Regression Shrinkage and Selection via the LASSO". Journal of the Royal Statistical Society. Series B (methodological) 58 (1). Wiley:
267-88, 1996.
[40] S. Stanković, I. Orović, and L. Stanković, “An Automated Signal Reconstruction Method based on Analysis of Compressive Sensed Signals in
Noisy Environment," Signal Processing, vol. 104, Nov 2014, pp. 43 - 50,
2014.
[41] S. G. Mallat, Z. Zhang, “Matching pursuits with time-frequency dictionaries,” IEEE Transactions on Signal Processing, vol. 41, no. 12, 1993, pp.
3397–3415.
[42] I. Daubechies, M. Defrise, C. De Mol "An iterative thresholding algorithm for linear inverse problems with a sparsity constraint," Communications on Pure and Applied Mathematics, Volume 57, Issue 11, November
2004, Pages 1413-1457.
[43] T. Blumensath, M. E. Davies, "Gradient Pursuits," IEEE Transactions on
Signal Processing, vol.56, no.6, pp.2370-2382, June 2008,
[44] M. A. Figueiredo, R. D. Nowak, S. J. Wright, “Gradient projection for
sparse reconstruction: Application to compressed sensing and other inverse problems,” IEEE Journal of Selected Topics in Signal Processing, vol. 1,
no. 4, 2007, pp. 586–597.
[45] E. Candès, J. Romberg, “`1 -magic : Recovery of Sparse Signals via
Convex Programming, ” Caltech, http://users.ece.gatech.edu/justin/
l1magic/downloads/l1magic.pdf, Oct.2005.
[46] L. Stanković, M. Daković, S. Vujović, “Adaptive Variable Step Algorithm
for Missing Samples Recovery in Sparse Signals,”IET Signal Processing,
vol. 8, no. 3, 2014. pp. 246 -256.
[47] L. Stanković, “A measure of some time–frequency distributions concentration,” Signal Processing, vol. 81, 2001, pp. 621–631.
[48] S. Stanković, I. Orović, and L. Stanković, "Polynomial Fourier Domain
as a Domain of Signal Sparsity," Signal Processing, Vol. 130, Jan. 2017, pp.
243-253.
[49] S. Stankovic, L. Stankovic, and I. Orovic, "Compressive sensing
approach in the Hermite transform domain," Mathematical Problems

32

Conditions for Unique Reconstruction

in Engineering, Volume 2015 (2015), Article ID 286590, 9 pages
http://dx.doi.org/10.1155/2015/286590.
[50] A. Sandryhaila, J. Kovacevic, M. Puschel, "Compression of QRS complexes using Hermite expansion", IEEE int. Conference on Acoust., Speech
and Signal Process., ICASSP, Prague, 2011, pp. 581-584.
[51] M. Brajović, I. Orović, M. Daković, and S. Stanković, "On the Parameterization of Hermite Transform with Application to the Compression of
QRS Complexes," Signal Processing, vol. 131, pp. 113-119, February 2017.
[52] M. Brajović, I. Orović, M. Daković, and S. Stanković, "Gradient-based
signal reconstruction algorithm in the Hermite transform domain," Electronics Letters, Vol. 52, no. 1, pp.41-43, 2016.
[53] S. Stanković, I. Orović, and A. Krylov, "Video Frames Reconstruction
based on Time-Frequency Analysis and Hermite projection method,"
EURASIP Journal on Advances in Signal Processing, Special Issue on TimeFrequency Analysis and its Application to Multimedia signals, Vol. 2010, Article ID 970105, 11 pages, 2010.
[54] I. Orović, S. Stanković, T. Chau, C. M. Steele, and E. Sejdić, "Timefrequency analysis and Hermite projection method applied to swallowing accelerometry signals," EURASIP Journal on Advances in Signal Processing, Vol. 2010, Article ID 323125, 7 pages, 2010.

