Indonesian
Journal
of
Electrical
Engineering
and
Computer
Science
V
ol.
1,
No
.
2,
F
ebr
uar
y
2016,
pp
.
329
341
DOI:
10.11591/ijeecs
.v1.i2.pp329-340
329
On
Spar
se
Compression
Comple
xity
of
Speec
h
Signals
A.
N.
Omara*
1
,
A.
A.
Hefna
wy
1
,
and
Abdelhalim
Zekr
y
2
1,2
Computers
and
Systems
Depar
tment,
Electronics
Research
Institute
,
Giza,
Egypt
3
Comm
unications
and
Electronics
Depar
tment,
F
aculty
of
Engineer
ing,
Ain
Shams
Univ
ersity
,
Cairo
,
Egypt
*Corresponding
author
,
e-mail:
ahmed
omar
a@er
i.sci.eg
Abstract
In
this
paper
,
w
e
ha
v
e
addressed
the
issue
of
the
sparse
compression
comple
xity
f
or
the
speech
signals
.
First
of
a
ll,
this
w
or
k
illustr
ated
the
eff
ect
of
the
signal
length
on
the
comple
xity
le
v
els
of
Matching
Pursuit
(MP)
and
Or
thogonal
Matching
Pursuit
(OMP)
algor
ithms
.
Also
,
this
paper
introduced
a
study
of
possibility
to
reduce
that
comple
xity
b
y
e
xploiting
the
shared
atoms
among
the
contiguous
speech
compres-
sions
.
By
compar
ing
the
shared
atoms
le
v
els
and
a
threshold
le
v
el
induced
b
y
an
analytic
model
based
on
the
both
the
centr
al
and
non-centr
al
h
yper-geometr
ic
distr
ib
utions
,
w
e
pro
v
ed
the
ability
of
the
shared
atoms
cr
iter
ion
to
detect
if
there
is
biasing
to
w
ards
a
subspace
of
atoms
or
not,
and
to
deci
de
if
the
biasing
occurs
due
to
the
redundancy
in
the
dictionar
y
of
atoms
,
or
due
to
the
redundancy
in
the
signal
itself
.
Moreo
v
er
,
w
e
suggested
a
subspace
bias-based
approaches
f
or
comple
xity
reduction
called
”A
toms
Reuse”
and
”Activ
e
Cluster”.
Both
methods
e
xploits
the
higher
le
v
els
of
the
shared
atoms
to
reduce
the
compression
comple
xity
b
y
reducing
the
search
space
dur
ing
the
pursuit
iter
ations
.
K
e
yw
or
ds:
Sparse
Compression
,
Speech
Signal,
Comple
xity
,
Shared
Atoms
,
Centr
al
and
Non-Centr
al
Hyper-Geometr
ic
Distr
ib
utions
Cop
yright
c
2016
Institute
of
Ad
v
anced
Engineering
and
Science
.
All
rights
reser
v
ed.
1.
Intr
oduction
No
w
ada
ys
,
one
of
the
efficient
signal
r
epresentations
is
the
sparse
modeling.
This
type
of
signal
decomposition
has
recently
receiv
ed
e
xtensiv
e
research
inte
rest
across
se
v
er
al
com-
m
unities
including
signal
processing,
inf
or
mation
theor
y
,
and
optimization
[1,
2,
3].
Also
,
these
representations
ha
v
e
f
ound
successful
applications
in
data
inter
pretation,
source
separ
ation,
sig-
nal
de-noising
,
coding,
classification,
recognition,
and
man
y
more
[4].
In
sparse
representation,
the
signal
can
be
constr
ucted
b
y
elementar
y
w
a
v
ef
or
ms
chosen
in
a
f
amily
called
a
dictionar
y
[5].
The
dictionar
y
elements
are
called
atoms
that
ma
y
be
or
thogonal
or
non-or
th
ogonal
[6].
The
o
v
er-completed
dictionar
ies
whose
atoms
are
larger
than
bases
are
needed
to
b
uild
sparse
repre-
sentations
of
comple
x
signals
[7].
But
choosing
is
difficult
and
requires
more
comple
x
algor
ithms
.
Letting
denotes
a
dictionar
y
matr
ix
of
siz
e
M
N
(where
typically
M
<
N
)
and
y
denotes
a
signal
v
ector
in
R
M
.
The
goal
of
sparse
decomposition
algor
ithms
such
as
Matching
Pursuit
(MP)
[8],
Or
thogonal
Matching
Pursuit
(OMP)
[9],
Optimiz
ed
Or
thogonal
Matching
Pursuit
(OOMP)
[10],
Bac
kw
ard-Optimiz
ed
Or
thogonal
Matching
Pursuit
BOOMP
[11],
and
others
is
to
reco
v
er
a
coefficient
v
ector
x
2
R
N
with
roughly
k
<
M
nonz
ero
ter
ms
so
that
x
equals
y
e
xactly
or
appro
ximately
.
y
'
x
(1)
Actually
,
the
af
orementioned
g
reedy
algor
ithms
and
others
are
mainly
concer
ned
with
decomposing
a
single
v
ector
sparsely
regardless
of
the
sign
al
is
a
unique
v
ector
or
splitted
to
man
y
v
ectors
.
Natur
ally
,
the
long
signals
such
as
speech
signals
should
be
splitted
to
F
fr
ames
or
v
ectors
inde
x
ed
b
y
Y
j
bef
ore
the
coding
process
.
So
,
the
sparse
appro
ximation
of
a
signal
Y
2
R
M
F
will
be
X
such
that
X
2
R
N
F
and
X
j
represents
the
sparse
decomposition
of
v
ector
Y
j
.
This
can
be
wr
itten
in
the
f
ollo
wing
f
or
m
Y
1
Y
2
Y
F
'
X
1
X
2
X
F
(2)
Receiv
ed
Dec
26,
2015;
Re
vised
J
an
19,
2016;
Accepted
F
eb
16,
2016
Evaluation Warning : The document was created with Spire.PDF for Python.
330
ISSN:
2502-4752
It
is
intuitiv
ely
ob
vious
that,
the
computational
comple
xity
of
(2)
is
larger
than
that
of
(1)
due
to
the
signal
length.
So
,
in
th
is
research,
w
e
initiate
a
ne
w
trend
in
the
comple
xity
reduction,
whose
main
idea
is
to
resiz
e
the
dictionar
y
of
atoms
dur
ing
the
pursuit
iter
ations
.
The
intended
sub-dictionar
y
is
the
subspace
of
atom
s
at
which
the
sparse
compressions
biases
to
w
ards
it.
So
,
in
this
w
or
k,
w
e
tr
y
to
e
xploit
some
of
the
F
v
ectors
to
detect
that
if
the
sparse
compressions
biases
to
a
subspace
of
atoms
or
not.
In
other
w
ords
,
the
signal
under
consider
ation
ma
y
liv
e
in
the
span
of
a
subspace
of
.
This
subspace
biasing
ma
y
occur
due
to
the
redunda
ncy
nature
of
the
speech
signal,
or
due
to
the
redundancy
nature
of
.
The
main
contr
ib
ution
of
this
paper
is
introducing
a
ne
w
cr
iter
ion
so-called
the
”Shared
Atoms”
that
can
be
monitored
dur
ing
the
successiv
e
sparse
compressions
and
then
w
e
can
decide
if
there
is
subspace
biasing
or
not.
Finally
,
this
paper
is
organiz
ed
as
f
ollo
ws
.
Section
2.
studies
the
eff
ect
of
the
signal
length
on
the
comple
xity
le
v
els
of
MP
and
OMP
algor
ithms
.
Section
3.
re
vie
ws
the
related
w
or
ks
on
enhancing
the
pursuit
algor
ithms
comple
xity
.
Section
4.
will
study
the
shared
atoms
cr
iter
ion
from
a
probability
standpoint
illustr
ating
its
e
xpected
le
v
els
and
bounds
.
Section
5.
will
illustr
ate
the
indications
of
the
shared
atoms
and
ho
w
w
e
can
benefit
from
it
in
achie
ving
a
satisfied
comple
xity
le
v
els
.
Section
6.
contains
e
xper
imental
results
.
Finally
,
conclusions
are
pro
vided
in
Section
7..
2.
Spar
se
Compression
Comple
xity
Since
t
he
pursuit
algor
ithms
don’t
consider
the
splitting
process
,
it
will
handle
each
v
ector
independently
.
So
,
it
is
logic
to
sa
y
that
there
are
thr
ee
comple
xity
le
v
els
.
The
first
le
v
el
is
called
the
”iter
ation-based
comple
xity”
and
depends
on
the
atom
choice
methodology
.
The
second
le
v
el
is
called
the
”sparsity-based
comple
xity”
and
depends
on
the
sparsity
le
v
el
k
or
the
n
umber
of
nonz
ero
elements
.
Both
comple
xity
le
v
els
are
considered
fix
ed
per
each
independent
decompo-
sition
if
and
only
if
the
sparse
modeling
arguments
are
identical
such
as
the
sparsity
le
v
el
k
and
the
dictionar
y
siz
e
N
.
Finally
,
The
third
comple
xity
le
v
el
is
due
to
the
o
v
er
all
decomposition
of
the
F
v
ectors
,
and
in
this
case
the
computational
comple
xity
depends
on
F
.
Gener
ally
,
the
time
comple
xity
T
of
an
y
pursuit
algor
ithm
could
be
denoted
as
O
(
G
)
where
the
function
G
represents
the
f
astest
g
ro
wing
ter
m
in
another
function
G
(
F
;
M
;
N
;
k
)
.
According
to
the
r
ule
of
the
big
O
notation
and
f
or
a
positiv
e
constant
"
the
upper
bound
of
T
can
be
obtained
as
f
ollo
ws
[12]:
T
"
G
(3)
Usually
,
the
function
G
represents
the
n
umber
of
the
elementar
y
ar
ithmetic
oper
ations
in
the
algor
ithm
such
as
the
m
ultiplications
G
and
the
additions
G
.
According
to
this
definition
the
function
G
could
be
represented
as
f
ollo
ws:
G
(
F
;
M
;
N
;
k
)
=
F
X
j
=1
k
X
i
=1
(
G
(
i
)
+
G
(
i
)
)
j
(4)
This
representation
of
G
means
that,
dur
ing
the
decomposition
of
v
ector
Y
j
,
both
G
(
i
)
and
G
(
i
)
represent
the
n
umber
of
the
elementar
y
oper
ations
at
the
i
th
iter
ation.
T
ab
le
1
summa-
r
iz
es
the
k
e
y
procedures
of
the
tw
o
most
common
algor
ithms
f
MP
,
OMP
g
and
their
par
ameters
f
G
(
i
)
;
G
(
i
)
g
.
As
sho
wn
in
the
tab
le
,
f
or
MP
algor
ithm,
the
computation
comple
xity
at
the
iter
ation
i
f
ocuses
on
the
procedure
T
r
i
1
.
This
procedure
calculates
the
correlation
betw
een
the
residual
error
r
i
1
of
the
pre
vious
iter
ation
and
the
N
elements
of
.
F
or
r
i
1
2
R
M
and
2
R
M
N
,
the
correlation
process
requires
N
v
ector
m
ultiplications
and
each
v
ector
m
ultiplication
consists
of
M
elementar
y
products
and
M
1
additions
.
As
illustr
ated
in
the
T
ab
le
1,
both
G
(
i
)
and
G
(
i
)
can
be
wr
itten
as
M
(
N
+
1)
+
N
and
M
(
N
+
1)
N
respectiv
ely
.
By
substituting
into
(4)
w
e
obtain
G
M
P
=
P
F
j
=1
P
k
i
=1
2
M
(
N
+
1)
j
.
Finally
,
the
function
G
can
be
wr
itten
in
the
f
or
m
G
M
P
=
2
F
k
M
N
1
+
1
N
(5)
IJEECS
V
ol.
1,
No
.
2,
F
ebr
uar
y
2016
:
329
341
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4752
331
Procedure
Routine
Subroutine
MP
OMP
G
(
i
)
G
(
i
)
G
(
i
)
G
(
i
)
Atom
Sel.
N
1
=
T
r
i
1
M
N
(
M
1)
N
or
(
i
)
=
T
(
i
)
r
i
1
M
(
N
i
+1)
1
M
1
(
N
i
+1)
1
'
i
=
ar
g
max
j
j
N
0
N
i
+
1
0
^
r
i
1
h
r
i
1
;
'
i
i
'
i
M
0
or
i
(
T
i
i
)
1
T
i
r
i
1
G
¸
=
T
i
i
M
i
2
(
M
1)
i
2
A
=
G
¸
1
i
3
i
3
2
i
2
+
i
B
=
i
A
M
i
2
M
(
i
2
i
)
C
=
B
T
i
M
2
i
M
2
(
i
1)
D
=
C
r
i
1
M
2
M
2
M
Err
Update
r
i
=
r
i
1
^
r
i
1
0
M
0
M
T
ab
le
1.
f
G
(
i
)
;
G
(
i
)
g
f
or
MP
and
OMP
As
sho
wn
in
(5),
the
f
astest
g
ro
wing
ter
m
consists
of
the
m
ultiplication
F
k
M
N
.
So
,
the
time
comple
xity
of
MP
can
be
represented
in
ter
ms
of
the
big
O
notation
b
y
T
M
P
=
O
(
F
k
M
N
)
.
If
w
e
k
eep
F
out
of
T
M
P
the
result
is
sim
ilar
to
t
he
pro
v
ed
comple
xit
y
e
xpressions
f
or
the
MP
algor
ithm
in
[13]
and
[14].
Unlik
e
MP
,
the
computation
comple
xity
of
OMP
at
the
iter
ation
i
is
distr
ib
uted
among
the
atom
selectio
n
and
the
coefficients
update
procedures
.
Note
that,
w
e
got
G
and
G
f
or
the
Gr
am
matr
ix
in
v
erse
G
¸
1
from
[15]
.
As
sho
wn
in
the
T
ab
le
1,
at
the
i
th
iter
ation,
the
algor
ithm
updates
tw
o
sets
sim
ultaneously
(
i
)
and
i
such
that
(
i
)
=
(
i
1)
f
'
i
1
g
,
i
=
i
1
[
f
'
i
g
and
the
initial
sets
are
(1)
=
and
0
=
;
,
where
;
ref
ers
here
to
the
empty
set
and
'
i
ref
ers
to
the
selected
atom
at
t
he
iter
ation
i
.
By
substituting
the
v
alues
of
G
(
i
)
and
G
(
i
)
into
(4)
w
e
obtain
G
O
M
P
appro
ximately
in
the
f
or
m
G
O
M
P
2
F
k
M
N
1
+
M
N
(6)
As
sho
wn
in
(6),
the
f
astest
g
ro
wing
ter
m
consists
of
the
m
ultiplication
F
k
M
N
.
So
,
the
time
comple
xity
of
OMP
can
be
represented
in
ter
ms
of
the
big
O
notation
b
y
T
O
M
P
=
O
(
F
k
M
N
)
.
3.
Related
W
ork
Ov
er
the
last
y
ears
,
man
y
methods
being
made
in
regards
to
reducing
the
comple
xity
le
v
els
of
the
sparse
pursuit
algor
ithms
.
The
major
ity
of
these
approaches
can
be
categor
iz
ed
into
f
our
g
roups
.
There
are
f
ast
tr
ansf
or
mation-based
methods
,
cluster
ing-based
methods
,
matr
ix
f
actor
ization-based
methods
and
optimization-based
methods
.
In
f
ast
tr
ansf
or
mation-
based
methods
,
the
pursuit
algor
ithm
e
xploits
the
f
ast
computations
proper
ty
of
the
F
ast
F
our
ie
r
T
r
ansf
or
ms
(FFT)[16],
or
the
F
ast
W
a
v
elet
T
r
ansf
or
ms
(FWT)[17].
The
basic
idea
behind
this
trend
is
to
use
pre-str
uctured
dictionar
ies
whose
atoms
are
theoretically
based,
such
as
F
our
ier
bases
and
w
a
v
elets
.
The
f
ast
tr
ansf
or
m
algor
ithms
reduces
the
n
umber
of
elementar
y
m
ultiplicat
ions
in
matr
ix-v
ector
product
of
T
r
i
1
from
M
N
to
N
l
og
M
.
Although
pre-
str
uctured
dictionar
ies
lead
to
f
ast
sparse
compressions
,
the
y
are
limited
in
their
ability
to
sparsify
the
signals
the
y
are
designed
to
handle
.
Fur
ther
more
,
most
of
those
dictionar
ies
are
restr
icted
to
signals
of
a
cer
tain
type
,
and
cannot
be
used
f
or
a
ne
w
and
arbitr
ar
y
f
amily
of
signals
of
interest.
On
Sparse
Compression
Comple
xity
of
Speech
Signals
(A.
N.
Omar
a)
Evaluation Warning : The document was created with Spire.PDF for Python.
332
ISSN:
2502-4752
In
cluster
ing-based
methods
,
the
approaches
e
xploit
the
correlation
proper
ty
among
the
atoms
of
.
Due
to
the
o
v
er-completeness
of
,
there
are
highly
correlated
atoms
that
ha
v
e
similar
proper
ties
.
So
,
b
y
means
of
cluster
ing
the
similar
atoms
be
g
rouped
in
a
cluster
and
this
procedure
reduces
the
search
time
in
those
clusters
.
F
or
e
xample
,
the
author
in
[18]
proposed
an
efficient
dictionar
y
organization
technique
.
This
technique
g
roups
similar
atoms
together
,
and
represent
them
b
y
a
unique
element
called
molecule
.
Applying
cluster
ing
recursiv
ely
on
atoms
and
molecules
yields
a
hier
archical
tree
str
ucture
,
which
can
be
e
xploited
to
design
a
search
algor
ithm
with
g
reatly
reduced
comple
xity
.
T
o
speed
up
the
processing
of
matr
ix
oper
ations
such
as
the
in
v
erse
of
g
r
am
matr
ix
G
¸
=
T
i
i
(see
T
ab
le
1),
there
are
diff
erent
matr
ix
f
actor
ization-based
methods
can
be
used
f
or
that
pur
pose
.
The
Cholesky-based
OMP
[19]
and
QR-based
OMP
[20]
use
the
Cholesky
and
QR
f
actor
ization
methods
respectiv
ely
to
reduce
the
comple
xit
y
of
G
¸
1
.
The
basic
idea
behind
Cholesky
f
actor
ization
is
to
decompose
a
Her
mitian,
positiv
e-definite
matr
ix
G
¸
into
the
product
of
a
lo
w
er
tr
iangular
matr
ix
G
¸
L
and
its
conjugate
tr
anspose
G
¸
T
L
.
While
the
basic
ide
a
behind
QR
f
actor
ization
is
to
decompose
a
real,
square
matr
ix
into
the
product
of
an
or
t
hogonal
matr
ix
Q
and
an
upper
tr
iangular
matr
ix
R.
In
optimization-ba
s
e
d
methods
,
the
approaches
tr
y
to
speed
up
the
or
thogonal
projection
process
needed
b
y
the
OMP
algor
ithm
to
update
the
coefficients
.
As
depicted
in
Section
2.,
the
diff
erence
in
comple
xity
betw
een
MP
and
OMP
algor
ithms
is
concentr
a
ted
in
the
coefficients
update
procedure
that
requires
to
solv
e
r
i
1
=
i
b
,
where
b
is
the
v
ector
of
unkno
wn
coefficients
.
The
or
iginal
OMP
solv
es
this
prob
lem
using
the
least
squares
method
b
=
(
T
i
i
)
1
T
i
r
i
1
.
F
ast
solv
ers
f
or
the
linear
equations
had
been
e
xploited
to
appro
ximate
the
or
thogonal
projection
of
the
least
squares
method,
f
or
e
xample
,
th
e
author
in
[21]
replaced
the
least
squares
method
b
y
another
f
ast
approaches
such
as
the
g
r
adient,
the
conjugate
g
r
adient
[22]
and
the
appro
ximate
conjugate
g
r
adient
methods
.
4.
Subspace
Bias-based
Efficient
Spar
se
Compression
As
sho
wn
in
the
liter
ature
re
vie
w
,
all
eff
or
ts
that
had
been
made
to
reduce
the
computa-
tional
comple
xity
ignored
the
nature
of
the
signal
under
consider
ation.
In
this
paper
,
w
e
will
study
the
possibility
to
e
xploit
the
redundancy
nature
of
t
he
speech
signal
and
the
dictionar
y
to
mak
e
an
efficient
sparse
compression.
W
e
seek
to
use
a
cr
iter
ion
called
the
”Shared
Atoms”
to
w
or
k
as
a
biasing
monitor
that
detect
if
there
is
biasing
t
o
w
ards
a
subspace
of
atoms
or
not,
and
decide
if
the
biasing
occurs
due
to
the
redundancy
in
the
dictionar
y
of
atoms
,
or
due
to
the
redundancy
in
the
signal
itself
or
due
to
both.
4.1.
Shared
atoms
Assume
that
=
f
'
n
;
n
2
g
is
a
dictionar
y
of
atoms
,
is
a
set
of
indices
.
Let
(
j
)
and
(
j
+
)
be
tw
o
suppor
t
sets
or
subsets
of
consisting
of
the
nonz
ero
elements
indices
in
X
j
and
X
j
+
respectiv
ely
such
that
is
the
neighborhood
deg
ree
to
the
inde
x
j
.
Then,
the
indices
of
the
shared
atoms
among
X
j
and
X
j
+
can
be
descr
ibed
as
(
j
)
\
(
j
+
)
=
f
'
n
;
n
2
(
j
)
and
n
2
(
j
+
)
g
(7)
Let
C
(
)
be
the
cardinality
of
the
intersection
set
in
(7)
or
the
n
umber
of
the
shared
atoms
,
and
giv
en
b
y
C
(
)
=
j
(
j
)
\
(
j
+
)
j
(8)
Also
,
this
cardinality
can
be
e
xpressed
as
k
X
j
X
j
+
k
0
where
the
notation
stands
f
or
the
Hadamard
(or
elementwise)
product
of
tw
o
v
ectors
.
Let
k
j
and
k
j
+
be
the
n
umber
of
the
non
z
ero
elements
in
X
j
and
X
j
+
respectiv
ely
or
the
n
umber
of
the
elements
in
(
j
)
and
(
j
+
)
respectiv
ely
,
then
the
maxim
um
v
alue
of
C
(
)
can
be
obtained
when
(
j
)
(
j
+
)
or
(
j
+
)
(
j
)
.
And
the
minim
um
v
alue
can
be
obtained
when
(
j
)
\
(
j
+
)
=
;
.
Mathematically
,
this
can
be
b
y
0
C
(
)
inf
f
k
j
;
k
j
+
g
.
If
k
j
=
k
j
+
=
k
,
then
w
e
ha
v
e
0
C
(
)
k
.
T
o
estimate
the
v
alue
of
C
(
)
,
let
P
(
C
(
)
=
j
(
j
)
)
denotes
the
probability
of
shared
atoms
among
X
j
and
IJEECS
V
ol.
1,
No
.
2,
F
ebr
uar
y
2016
:
329
341
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4752
333
X
j
+
,
giv
en
the
subset
(
j
)
with
cardinality
k
j
.
Then
the
e
xpected
v
alue
of
C
(
)
is
giv
en
b
y
E
C
(
)
=
P
k
j
+
=0
P
(
C
(
)
=
j
(
j
)
)
.
4.1.1.
Unbiased
case
F
or
a
redundant
consisting
of
N
atoms
,
assume
that
all
N
atoms
ha
v
e
the
same
chance
dur
ing
the
selection
procedure
,
i.e
.
the
y
are
chosen
unif
or
mly
and
some
what
r
andomly
without
replacement.
Then
the
e
xpected
v
alue
of
C
(
)
can
be
e
xpressed
in
ter
ms
of
the
centr
al
h
yper-
geometr
ic
distr
ib
ution
E
C
(
)
=
k
j
+
X
=0
k
j
N
k
j
k
j
+
N
k
j
+
(9)
So
,
the
e
xpected
v
alue
is
e
xpressed
b
y
E
C
(
)
=
k
j
+
k
j
N
.
F
or
the
case
k
j
=
k
j
+
=
k
,
w
e
ha
v
e
E
C
(
)
=
k
2
N
,
and
the
probability
t
o
obtain
the
upper
bound
of
C
(
)
is
giv
en
b
y
P
(
C
(
)
=
k
j
(
j
)
)
=
1
N
k
.
This
probability
reaches
its
maxim
um
v
alue
when
N
=
k
b
ut
this
condition
is
not
pr
actical.
F
or
an
y
sparse
compression,
th
e
n
umber
of
atoms
N
m
ust
be
g
reater
than
the
dimension
of
the
signal
M
which
is
natur
ally
g
reater
than
k
.
On
the
other
side
,
the
probability
of
z
ero
shared
atoms
is
giv
en
b
y
P
(
C
(
)
=
0
j
(
j
)
)
=
N
k
k
N
k
,
and
this
probability
reaches
its
maxim
um
v
alue
f
or
the
condition
N
k
.
4.1.2.
Biased
case
Assume
each
atom
in
(
j
)
has
the
w
eight
!
1
,
and
each
atom
in
(
j
)
has
the
w
eight
!
2
.
Then,
the
e
xpected
v
alue
of
C
(
)
can
be
e
xpressed
in
ter
ms
of
the
W
allenius
non-centr
al
h
yper-geometr
ic
distr
ib
ution
[23]
E
C
(
)
=
k
j
+
X
=0
k
j
N
k
j
k
j
+
1
Z
0
f
(
t
)
dt
(10)
where
,
f
(
t
)
=
1
t
!
=
(1
t
1
=
)
k
j
+
;
!
=
!
1
!
2
,
”Odds
Ratio”
(11)
=
!
(
k
j
)
+
(
N
k
j
k
j
+
+
)
(12)
As
illustr
ated
in
[24],
the
e
xpected
v
alue
of
the
W
allenius
distr
ib
ution
is
appro
ximated
b
y
solution
E
C
(
)
to
1
E
C
(
)
k
j
=
1
k
j
+
E
C
(
)
N
k
j
!
(13)
F
or
the
case
of
equal
iter
ations
,
the
Equation
(13)
can
be
re
wr
itten
as
f
ollo
ws
1
E
C
(
)
k
=
1
k
E
C
(
)
N
k
!
(14)
F
rom
(14)
w
e
can
obtain
the
bounds
of
E
C
(
)
at
the
bounds
of
!
.
When
!
tends
to
infinity
,
i.e
.,
!
1
!
2
then
the
r
ight-hand
side
(RHS)
ter
m
equals
0
because
the
v
ar
iab
le
within
the
br
ac
k
ets
is
less
than
1
,
and
then
E
C
(
)
equals
k
.
But
f
or
!
0
,
i.e
.,
!
2
!
1
,
the
RHS
ter
m
equals
1,
and
then
E
C
(
)
equals
0
.
On
Sparse
Compression
Comple
xity
of
Speech
Signals
(A.
N.
Omar
a)
Evaluation Warning : The document was created with Spire.PDF for Python.
334
ISSN:
2502-4752
5.
The
Indications
of
C
(
)
And
The
Benefits
One
of
th
e
main
conclusions
of
Section
4.1.
w
as
that,
as
long
as
the
redundant
dictionar
y
consisting
of
finite
n
umber
of
atoms
N
,
there
is
inherent
s
h
ared
atoms
among
the
successiv
e
compressions
(
X
j
;
X
j
+1
)
regardless
of
the
redundancy
in
the
signal
and
the
dict
ionar
y
.
Bef
ore
e
xper
iments
are
conducted
to
measure
C
(
)
,
this
section
will
illustr
ate
the
indications
of
the
shared
atoms
according
to
its
le
v
el
and
its
dependency
on
.
5.1.
Pr
obab
le
le
vels
of
C
(
)
F
rom
Equation
(13),
w
e
can
conclude
the
probab
le
le
v
els
of
C
(
)
according
to
the
odds
r
atio
!
as
f
ollo
ws
E
C
(
)
=
k
j
+
k
j
N
;
!
=
1
E
C
(
)
>
k
j
+
k
j
N
;
!
>
1
E
C
(
)
<
k
j
+
k
j
N
;
!
<
1
(15)
The
proof
of
(15)
is
giv
en
in
(A).
As
sho
wn,
one
of
the
probab
le
le
v
els
of
C
(
)
is
the
h
yper-
geometr
ic
mean
k
j
k
j
+
=
N
.
This
le
v
el
is
considered
a
special
case
and
indicates
that
all
N
atoms
of
are
in
use
and
there
is
no
bias
to
an
y
subset
of
atoms
.
The
most
impor
tant
le
v
el
of
C
(
)
is
that
at
which
the
shared
atoms
are
g
reater
than
k
j
k
j
+
=
N
.
In
this
case
,
the
shared
atoms
indicates
that
there
is
some
what
bias
to
a
subset
of
atoms
in
the
space
.
5.2.
Compression
comple
xity
and
C
(
)
The
bias
proper
ty
of
C
(
)
ma
y
lead
us
to
tw
o
diff
erent
trends
in
the
compression
com-
ple
xity
reduction.
The
first
trend
is
called
”Atoms
Reuse”,
and
the
second
is
called
”Activ
e
Cluster”.
T
o
justify
the
impor
tance
of
measur
ing
C
(
)
,
let
us
illustr
ate
the
enhancement
le
v
els
in
comple
xity
which
ma
y
get
them
if
w
e
ha
v
e
benefited
from
C
(
)
.
5.2.1.
Atoms
Reuse
Lik
e
the
contiguous
pix
els
in
image
signal,
the
contiguous
speech
fr
ames
ma
y
ha
v
e
com-
mon
f
eatures
.
I
f
the
atoms
in
ha
v
e
the
ability
to
descr
ibe
diff
erent
signal
f
eatures
,
then
w
e
can
e
xpect
that
the
le
v
el
of
C
(
)
are
g
re
ater
than
the
threshold
le
v
el
k
j
k
j
+
=
N
,
and
there
are
atoms
can
be
reused
among
the
contiguous
speech
compressions
.
Proposition
1:
Assume
k
j
=
k
j
+
=
k
,
if
the
MP
algor
ithm
is
f
orced
to
select
atoms
from
the
current
suppor
t
set
(
j
)
in
the
ne
xt
compression,
then
the
relativ
e
enhancement
in
comple
xity
reaches
up
to
k
(1
k
N
)
.
As
f
or
the
OMP
algor
ithm,
the
relativ
e
enhancement
in
G
O
M
P
is
slightly
less
than
that
in
G
M
P
and
depends
on
the
signal
dimension
M
.
The
proof
is
giv
en
in
(B)
and
(C).
5.2.2.
Active
Cluster
If
C
(
)
is
g
reater
than
k
j
+
k
j
=
N
regardless
of
,
then
w
e
can
sa
y
that
there
is
biasing
to
w
ards
diff
erent
subsets
of
atoms
,
and
there
is
an
activ
e
subspace
0
.
Definition:
In
this
paper
,
w
e
will
define
the
efficiency
of
the
space
b
y
=
k
j
k
j
+
=C
(
)
N
Proposition
2:
Assume
k
j
=
k
j
+
=
k
,
if
there
are
F
0
fr
ames
m
ust
be
compressed
bef
ore
detect
-
ing
the
activ
e
cluster
0
with
cardinality
j
0
j
=
N
0
,
such
that
the
remaind
er
fr
ames
(
F
F
0
)
are
compressed
using
the
subspace
0
.
Then
the
relativ
e
enhancement
in
the
comple
xity
reaches
to
(1
)(1
1
)
,
and
(1
)(1
2
)
f
or
MP
and
OMP
respectiv
ely
,
where
,
,
1
and
2
represent
the
r
atios
F
0
F
,
N
0
N
,
1+1
=
N
0
1+1
=
N
and
1+
M
=
N
0
1+
M
=
N
respectiv
ely
.
The
proof
is
giv
en
in
(D)
and
(E).
Note
that,
in
this
paper
w
e
do
not
care
about
ho
w
w
e
select
the
N
0
atoms
from
the
dictionar
y
,
b
ut
w
e
consider
only
its
eff
ect
on
the
relativ
e
comple
xity
.
6.
Experimental
Results
After
declar
ing
the
impor
tance
of
C
(
)
in
the
Subsections
5.2.1.
and
5.2.2.,
in
this
section
w
e
will
present
a
set
of
e
xper
iment
results
.
The
intention
of
these
e
xper
iments
is
to
illustr
ate
the
IJEECS
V
ol.
1,
No
.
2,
F
ebr
uar
y
2016
:
329
341
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4752
335
0
0.2
0.4
0.6
0.8
1
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
k
2
/N
MP
OMP
Figure
1.
Exp
.(1).
C
k
vs
.
k
M
=
0
:
1
;
:::;
0
:
9
T
ab
le
2.
Exp
.(1).
!
vs
.
k
M
k
M
No
bias
M
P
O
M
P
le
v
el
0
:
1
1
0
:
853
1
:
015
0
:
2
1
1
:
013
1
:
009
0
:
3
1
0
:
991
0
:
94
0
:
4
1
0
:
993
0
:
995
0
:
5
1
0
:
962
0
:
975
0
:
6
1
0
:
924
0
:
963
0
:
7
1
0
:
939
0
:
982
0
:
8
1
0
:
917
0
:
986
0
:
9
1
0
:
927
1
:
007
ability
of
the
shared
atoms
cr
iter
ion
to
detect
the
e
xistence
of
the
subspace
biasing
and
to
sho
w
the
impact
of
the
signal
redundancy
and
the
dictionar
y
redundancy
on
the
biasing
le
v
els
.
All
e
x-
per
iments
use
the
most
common
sparse
algor
ithms
MP
and
OMP
and
w
ere
designed
in
MA
TLAB
en
vironment
using
the
sparse
compression
toolbo
x.
Also
,
all
sim
ulations
use
the
ISOLET
speech
database
[25],
and
the
main
par
ameters
of
the
sparse
compressions
are
M
=
100
,
pre-str
uctured
dictionar
y
with
N
=
512
and
finally
the
sparsity
le
v
el
k
r
anges
from
10
to
90
nonz
ero
elements
.
T
o
f
acilitate
compar
ison,
w
e
ha
v
e
nor
maliz
ed
k
and
C
(
)
b
y
dividing
all
them
b
y
their
maxim
um
le
v
el
M
and
k
respectiv
ely
.
6.1.
Experiment
1
:
Bias
of
(
j
+
)
to
a
random
set
(
r
)
In
this
e
xper
iment,
the
set
(
j
)
is
replaced
with
another
set
(
r
)
whose
k
elements
are
unif
or
mly
selected
from
t
he
whole
elements
of
the
dictionar
y
.
So
,
the
function
C
will
represent
the
cardinality
of
(
r
)
\
(
j
+
)
.
Figure
(1)
illustr
ates
that,
the
a
v
er
age
v
alues
of
C
(
)
are
appro
x-
imately
identical
to
the
e
xpected
v
alues
dete
r
mined
b
y
the
centr
al
h
yper-geometr
ic
distr
ib
ution,
and
this
result
indicates
that
there
is
no
bias
to
w
ards
the
r
andomly
selected
subsets
(
r
)
.
W
e
used
the
t
test
f
or
compar
ing
the
means
and
the
result
sho
w
ed
that
the
v
alues
of
sig
par
ame-
ter
are
g
reater
than
0
:
05
and
equal
0
:
886
,
0
:
975
f
or
MP
and
OMP
respectiv
ely
which
scientifically
means
that
the
v
ar
ia
bility
is
not
significantly
diff
erent.
Note
that,
w
e
can
obtain
the
bias
le
v
el
ac-
cording
to
the
v
alue
of
the
odds
r
atios
”
!
”
that
can
be
obtained
directly
from
Equation
(14)
to
be
!
=
log
(1
C
k
)
log
(1
k
C
N
k
)
.
As
e
videnced
b
y
T
ab
le
2,
the
odds
r
atio
con
v
erges
to
the
”No
bias”
le
v
el
or
1
f
or
all
k
=
M
v
alues
.
This
result
illustr
ated
that,
there
is
no
bias
to
an
y
r
andomly
selected
k
atoms
.
6.2.
Experiment
2
:
Bias
of
(
j
+
)
to
(
j
)
In
the
second
e
xper
iment
w
e
will
tr
y
to
measure
C
(
)
in
tw
o
cases
.
In
first
case
,
w
e
will
measure
it
when
the
positions
of
Y
j
in
the
matr
ix
Y
are
left
unchanged.
In
this
case
,
the
function
C
(
)
tak
es
into
consider
ations
the
chronological
order
of
fr
ames
.
On
the
contr
ar
y
,
in
the
second
case
,
w
e
will
measure
the
shared
atoms
when
the
positions
of
Y
j
in
Y
are
changed
to
ignore
the
eff
ect
of
the
chronological
order
of
speech
fr
ames
,
and
to
chec
k
the
efficiency
of
the
space
of
atoms
.
In
both
cases
,
w
e
chose
the
fifth
order
polynomial
f
or
fitting
the
measurements
of
C
(
)
f
or
=
1
to
50
.
Figure
(3)
illustr
ates
that,
the
chronological
order
of
Y
j
has
a
g
reat
eff
ect
on
C
(
)
.
F
or
the
first
case
,
C
(
)
deg
r
ades
as
increases
.
Also
,
it
is
noted
that
C
(1)
is
the
maxim
um
v
alue
which
means
that
the
largest
shared
atoms
occurs
among
the
adjacent
decompositions
.
This
case
is
in
star
k
contr
ast
to
the
second
case
,
as
sho
wn
in
Figure
(4),
the
v
alues
of
C
(
)
tends
to
constant
le
v
els
f
or
all
v
alues
of
.
This
result
illustr
ates
the
absence
of
t
he
chronological
order
of
Y
j
and
its
eff
ect
on
C
(
)
.
It
is
also
interesting
to
note
that
all
v
alues
of
C
(
)
are
larger
than
the
centr
al
h
yper-geometr
ic
threshold
le
v
el
k
2
=
N
which
means
that
the
odds
r
atios
of
the
W
allenius
On
Sparse
Compression
Comple
xity
of
Speech
Signals
(A.
N.
Omar
a)
Evaluation Warning : The document was created with Spire.PDF for Python.
336
ISSN:
2502-4752
0
0.2
0.4
0.6
0.8
1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
MP
OMP
Figure
2.
Exp
.(2),
case
2.
vs
.
k
M
=
0
:
1
;
:::;
0
:
9
T
ab
le
3.
Exp
.(2),
case
2.
!
vs
.
k
M
k
M
No
bias
M
P
O
M
P
le
v
el
0
:
1
1
5
:
278
4
:
936
0
:
2
1
3
:
425
3
:
239
0
:
3
1
2
:
707
2
:
604
0
:
4
1
2
:
312
2
:
258
0
:
5
1
2
:
057
2
:
039
0
:
6
1
1
:
874
1
:
896
0
:
7
1
1
:
732
1
:
816
0
:
8
1
1
:
618
1
:
78
0
:
9
1
1
:
521
1
:
786
distr
ib
ution
are
g
reater
than
1
.
T
ab
le
3
sho
ws
the
odds
r
atio
le
v
els
f
or
the
second
case
results
.
The
v
alues
of
the
odds
r
atios
pro
v
ed
that,
the
bias
proper
ty
is
clear
ly
visib
le
at
the
lo
w
le
v
els
of
k
=
M
,
b
ut
the
odds
r
atios
are
slightly
more
than
the
”No
bias”
le
v
el
at
the
higher
sparsity
le
v
els
.
0
10
20
30
40
50
0.12
0.13
0.14
0.15
0.16
0.17
MP
OMP
(a)
k
=
M
=
0
:
1
0
10
20
30
40
50
0.16
0.17
0.18
0.19
0.2
0.21
MP
OMP
(b)
k
=
M
=
0
:
3
0
10
20
30
40
50
0.195
0.2
0.205
0.21
0.215
0.22
0.225
MP
OMP
(c)
k
=
M
=
0
:
5
Figure
3.
Exp
.(2),
case
1:
C
=k
vs
.
=
1
;
:::;
50
0
10
20
30
40
50
0.13
0.132
0.134
0.136
0.138
0.14
0.142
MP
OMP
(a)
k
=
M
=
0
:
1
0
10
20
30
40
50
0.165
0.17
0.175
0.18
0.185
0.19
0.195
0.2
MP
OMP
(b)
k
=
M
=
0
:
3
0
10
20
30
40
50
0.195
0.2
0.205
0.21
0.215
0.22
0.225
MP
OMP
(c)
k
=
M
=
0
:
5
Figure
4.
Exp
.(2),
case
2:
C
=k
vs
.
=
1
;
:::;
50
The
results
of
both
cases
confir
med
that,
there
are
tw
o
types
of
subspace
biasing.
First
type
of
bias
is
called
”
based
bias”,
and
this
bias
mak
es
C
(
)
to
change
slightly
with
respect
to
.
While
the
other
type
is
called
”
0
based
bias”,
and
this
bias
mak
es
C
(
)
to
ha
v
e
significant
v
alues
g
reater
than
k
2
=
N
regardless
of
.
Finally
,
Figure
(2)
sho
ws
the
dictionar
y
efficiency
f
or
diff
erent
v
alues
of
k
=
M
.
As
sho
wn
in
the
figure
,
the
pre-str
uctured
dictionar
y
ha
v
e
efficiencies
r
anges
appro
ximately
from
20%
to
70%
.
6.3.
Experiment
3
:
Speec
h
redundanc
y
and
shared
atoms
As
illustr
ated
in
the
results
of
the
second
e
xper
iment,
th
e
suggested
cr
it
er
ion
C
(
)
ref
ers
to
a
little
bias
to
the
contiguous
suppor
t
set,
a
nd
this
result
is
logic
because
the
pre-str
uctred
IJEECS
V
ol.
1,
No
.
2,
F
ebr
uar
y
2016
:
329
341
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4752
337
0
0.2
0.4
0.6
0.8
1
0.12
0.14
0.16
0.18
0.2
0.22
0.24
0.26
0.28
0.3
MP−C(1)
MP−C
eo
OMP−C(1)
OMP−C
eo
Figure
5.
C
(1)
k
&
C
eo
k
vs
.
k
M
=
0
:
1
;
:::;
0
:
9
T
ab
le
4.
Exp
.(3).
!
vs
.
k
=
M
k
M
No
bias
M
P
O
M
P
le
v
el
C
(1)
C
eo
C
(1)
C
eo
0
:
1
1
8
:
52
19
:
2
8
:
09
20
:
72
0
:
2
1
4
:
83
8
:
18
4
:
45
8
:
69
0
:
3
1
3
:
51
5
:
01
3
:
24
5
:
27
0
:
4
1
2
:
82
3
:
63
2
:
62
3
:
78
0
:
5
1
2
:
41
2
:
89
2
:
25
2
:
97
0
:
6
1
2
:
13
2
:
42
2
:
04
2
:
49
0
:
7
1
1
:
93
2
:
11
1
:
9
2
:
24
0
:
8
1
1
:
77
1
:
9
1
:
84
2
:
11
0
:
9
1
1
:
65
1
:
74
1
:
83
2
:
06
atoms
”w
a
v
elet
basis”
are
local
d
escr
iptors
.
So
,
in
this
e
xper
iment
w
e
will
tr
y
to
remeasure
the
shared
atoms
among
the
highly
correlated
fr
ames
.
W
e
will
use
a
channel
splitting
technique
in
[26]
to
e
xtr
act
tw
o
highly
correlated
fr
ames
instead
o
f
the
sequential
splitting
procedure
used
in
the
pre
vious
e
xper
iment.
T
o
e
xtr
act
tw
o
highly
correlated
fr
ames
based
on
the
idea
[
26],
w
e
will
split
the
signal
Y
2
R
M
F
to
tw
o
signals
,
e
v
en
samples
signal
Y
e
2
R
M
d
F
2
e
,
and
odd
samples
signal
Y
o
2
R
M
d
F
2
e
.
The
corresponding
sparse
coefficients
matr
ices
will
be
X
e
2
R
N
d
F
2
e
and
X
o
2
R
N
d
F
2
e
respectiv
ely
.
In
this
e
xper
iment
w
e
will
measure
the
a
v
er
age
v
alues
of
C
eo
i
such
that
C
eo
i
=
k
X
e
i
X
o
i
k
0
.
Note
that,
X
e
i
and
X
o
i
are
the
column
v
ectors
in
X
e
and
X
o
respectiv
ely
.
Figure
(5)
illustr
ates
the
eff
ect
of
speech
splitting
on
the
le
v
el
of
the
shared
atoms
.
As
depicted
in
figure
,
the
e
v
en-odd
splitting
method
increases
the
shared
atoms
significantly
at
the
lo
w
sparsity
le
v
el.
But,
at
the
higher
le
v
els
of
k
=
M
the
v
alues
of
C
=k
con
v
erges
slightly
to
that
le
v
els
of
the
second
e
xper
iment.
As
f
or
the
eff
ect
of
the
e
v
en-odd
splitting
on
the
biasing
le
v
els
,
T
ab
le
4
illustr
ates
that
the
redundancy
among
the
contiguous
speech
samples
increased
the
odds
r
atios
significantly
at
the
lo
w
er
sparsity
le
v
els
.
7.
Conc
lusions
and
Future
w
orks
In
this
research,
a
par
ticular
attention
w
as
paid
to
the
sparse
compression
comple
xity
of
the
speech
signal.
In
the
first
par
t
of
this
paper
,
w
e
illustr
ate
d
the
eff
ect
of
the
signal
length
F
on
the
computational
comple
xity
G
.
As
sho
wn
in
Section
2.,
the
comple
xity
le
v
els
increased
linear
ly
from
O
(
k
M
N
)
to
O
(
F
k
M
N
)
.
If
w
e
look
deeply
into
the
m
ultiplication
ter
m
F
k
M
N
,
w
e
can
see
that
F
,
k
and
M
are
unchangeab
le
par
ameters
.
F
or
this
reason,
w
e
ha
v
e
sought
to
e
xploit
the
redundancy
of
the
dictionar
y
and
the
redundancy
of
the
signal
itself
to
resiz
e
according
to
the
biasing
of
the
sparse
compressions
to
w
ards
a
subspace
of
atoms
.
In
this
paper
w
e
ha
v
e
suggested
tw
o
subspace
bias-based
approaches
that
resiz
e
the
dictionar
y
dur
ing
the
iter
ations
either
b
y
f
orcing
the
algor
ithm
to
sele
ct
some
atoms
from
the
last
suppor
t
set
such
as
in
the
”Atoms
Reuse”
approach,
or
b
y
ignor
ing
some
atoms
from
the
whole
dictionar
y
such
as
in
the
so-called
”Activ
e
Cluster”
approach.
Since
both
approaches
are
applicab
le
if
there
is
some
what
biasing
to
w
ards
subspace
of
atoms
,
in
this
research,
w
e
do
not
care
about
applying
the
approaches
,
b
ut
w
e
considered
only
ho
w
to
detect
the
biasing.
So
,
w
e
ha
v
e
suggested
the
”Shared
Atoms”
cr
iter
ion
that
can
be
measured
th
rough
the
successiv
e
compressions
and
then
w
e
can
decide
if
there
is
biasing
to
w
ards
a
subspace
of
atoms
or
not
according
to
the
gap
betw
een
the
measured
le
v
el
and
the
analytic
le
v
el
k
2
=
N
.
Through
the
e
xper
imental
results
of
Section
6.,
w
e
ha
v
e
concluded
that
the
suggested
cr
iter
ion
ha
v
e
the
ability
to
detect
the
subspace
biasing.
Also
,
it
w
as
e
vident
that
the
biasing
ap-
pears
significantly
at
the
lo
w
er
sparsity
le
v
els
and
par
tially
disappear
at
the
higher
le
v
els
.
More-
o
v
er
,
the
odds
r
atios
illustr
ated
that
the
biasing
le
v
els
due
to
the
dictionar
y
redundancy
r
anges
appro
ximately
from
2
to
5
f
or
k
M
60%
.
But,
f
or
the
signal
redundancy
,
it
r
anges
from
2
to
20
f
or
On
Sparse
Compression
Comple
xity
of
Speech
Signals
(A.
N.
Omar
a)
Evaluation Warning : The document was created with Spire.PDF for Python.
338
ISSN:
2502-4752
k
M
60%
.
These
results
encour
aged
us
to
e
xtend
the
research
in
the
future
to
implement
the
approaches
and
to
study
the
impact
of
the
dictionar
y
resizing
on
the
final
appro
ximation
error
and
on
the
quality
of
the
speech
signal.
Fur
ther
more
,
w
e
seek
to
join
betw
een
the
unkno
wn
elements
of
the
activ
e
subspace
0
and
the
union
of
diff
erent
shared
atoms
,
and
to
join
betw
een
the
n
umber
of
those
elements
and
the
measured
efficiency
of
the
dictionar
y
.
Ref
erences
[1]
P
.
Fldik
and
P
.
Fiildihk,
“F
or
ming
sparse
representations
b
y
local
anti-heb
bian
lear
ning,
”
Bio-
logical
Cyber
netics
,
v
ol.
64,
pp
.
165–170,
1990.
[2]
M.
S
.
Le
wic
ki,
T
.
J
.
Sejno
wski,
and
H.
Hughes
,
“Lear
ning
o
v
ercomplete
representations
,
”
Neur
al
Computation
,
v
ol.
12,
pp
.
337–365,
1998.
[3]
J
.
A.
T
ropp
,
“T
opics
in
sparse
appro
ximation,
”
Ph.D
.
disser
tation,
The
Univ
ersity
of
T
e
xas
at
A
ustin,
A
ugust
2004.
[4]
W
.
Dai,
T
.
Xu,
and
W
.
W
ang,
“Sim
ultaneous
code
w
ord
optimization
(simco)
f
or
dictionar
y
update
and
lear
ning,
”
Signal
Processing,
I
EEE
T
r
ansactions
on
,
v
ol.
60,
no
.
12,
pp
.
6340–
6353,
Dec
2012.
[5]
S
.
Mallat,
A
w
a
v
elet
tour
of
signal
processing
,
3rd
ed.
Academic
Press
,
2009.
[6]
D
.
L.
Donoho
and
M.
Elad,
“Optimally
sparse
representation
in
gener
al
(nonor
thogonal)
dic-
tionar
ies
via
1
minimization
,
”
Proceedings
of
the
Na
tional
Academ
y
of
Sciences
,
v
ol.
100,
no
.
5,
pp
.
2197–2202,
2003.
[7]
J
.-J
.
Fuchs
,
“On
sparse
representations
in
arbitr
ar
y
redundant
bases
,
”
Inf
or
mation
Theor
y
,
IEEE
T
r
ansactions
on
,
v
ol.
50,
no
.
6,
pp
.
1341–1344,
J
une
2004.
[8]
S
.
Mallat
and
Z.
Zhang,
“Matching
pursuit
with
time-frequency
dictionar
ies
,
”
IEEE
T
r
ansac-
tions
on
Signal
Processing
,
v
ol.
41,
pp
.
3397–3415,
1993.
[9]
Y
.
C
.
P
ati,
R.
Rezaiif
ar
,
Y
.
C
.
P
.
R.
Rezaiif
ar
,
and
P
.
S
.
Kr
ishnapr
asad,
“Or
thogonal
matching
pursuit:
Recursiv
e
function
appro
ximation
with
applications
to
w
a
v
elet
decomposition,
”
in
Proceedings
of
the
27
th
Ann
ual
Asilomar
Conf
erence
on
Signals
,
Systems
,
and
Computers
,
1993,
pp
.
40–44.
[10]
L.
Rebollo-Neir
a
and
D
.
Lo
w
e
,
“Optimiz
ed
or
thogonal
matching
pursuit
approach,
”
Signal
Processing
Letters
,
IEEE
,
v
ol.
9,
no
.
4,
pp
.
137–140,
Apr
il
2002.
[11]
M.
Andr
le
,
L.
Rebollo-Neir
a,
and
E.
Sagianos
,
“Bac
kw
ard-optimiz
ed
or
thogonal
matching
pursuit
approach,
”
Signal
Processing
Letters
,
IEEE
,
v
ol.
11,
no
.
9,
pp
.
705–708,
Sept
2004.
[12]
V
.
V
.
Munis
w
am
y
,
Design
and
Analysis
of
Algor
ithms
.
Ne
w
Delhi,
India,
India:
I
K
Inter
na-
tional
Pub
lishing
House
,
2009.
[13]
B
.
Mailh,
R.
Gr
ibon
v
al,
P
.
V
anderghe
ynst,
and
F
.
Bimbot,
“F
ast
or
thogonal
sparse
appro
xima-
tion
algor
ithms
o
v
er
local
dictionar
ies
,
”
Signal
Processing
,
v
ol.
91,
no
.
12,
pp
.
2822
–
2835,
2011.
[14]
T
.
Blumensath
and
M.
Da
vies
,
“Gr
adient
pursuits
,
”
Signal
Processing,
IEEE
T
r
ansactions
on
,
v
ol.
56,
no
.
6,
pp
.
2370–2382,
J
une
2008.
[15]
H.
Anton
and
C
.
Rorres
,
Elementar
y
Linear
Algebr
a:
Applicat
ions
V
ersion
.
John
Wile
y
&
Sons
,
2010.
[16]
J
.
Coole
y
and
J
.
T
uk
e
y
,
“An
algor
ithm
f
or
the
machine
calculation
of
comple
x
f
our
ier
ser
ies
,
”
Mathematics
of
Computation
,
v
ol.
19,
no
.
90,
pp
.
297–301,
1965.
[17]
G.
Be
ylkin,
R.
Coifman,
and
V
.
Rokhlin,
“F
ast
w
a
v
elet
tr
ansf
or
ms
and
n
umer
ical
algor
ithms
I,
”
Comm.
Pure
Appl.
Math.
,
v
ol.
44,
pp
.
141–183,
1991.
[18]
P
.
Jost,
P
.
V
anderghe
ynst,
and
P
.
F
rossard,
“T
ree-based
pursuit:
Algor
ithm
and
proper
ties
,
”
Signal
Processing,
IEEE
T
r
ansactions
on
,
v
ol.
54,
no
.
12,
pp
.
4685–4697,
Dec
2006.
[19]
S
.
Cotter
,
R.
Adler
,
R.
Rao
,
and
K.
Kreutz-Delgado
,
“F
orw
ard
sequential
algor
ithms
f
or
best
basis
selection,
”
Vision,
Image
and
Signal
Processing,
IEE
Proceedings
-
,
v
ol.
146,
no
.
5,
pp
.
235–244,
Oct
1999.
[20]
S
.
Mallat
and
Z.
Zhang,
“Adaptiv
e
time-frequency
decomposition
with
matching
pursuits
,
”
in
Time-F
requency
and
Time-Scale
Analysis
,
1992.,
Proceedings
of
the
IEEE-SP
Inter
national
Symposium
,
Oct
1992,
pp
.
7–10.
IJEECS
V
ol.
1,
No
.
2,
F
ebr
uar
y
2016
:
329
341
Evaluation Warning : The document was created with Spire.PDF for Python.