l.
I)
0
:s
IS
d
d
)0
IT
~8
•a!
'1
nd
he
)C.
en
an
p .
e
Y,
on
y,
o
o
h
he
on
md
00,
SIGNAL
PROCESSING
V:
Theo ies
and
Applica ions
L.
To es,
E.
Masg au,
and
M.A.
Lagunas
(eds.)
©
Else /e
Science
Publishe s
8.
V.,
1990
349
A SIGNAL SUBSPACE
FRAMEWORK
OF
NONLINEAlUY
CONSTRAINED SOLUTIONS
S.
Konyk, J .*,
M.
G. Amin*,
M.
A.
Lagunas*•
*Depa men o Elec ical Enginee ing
Villano a Uni e si y
Villano a, PA 19085, USA
**
P ocesado de Senal en Comunicaciones
E.T.S.I. Telecomunicacion
Apdo.
30.002
08080
Ba celona, Spain
A signal subspace based amewo k in p esen ed o he nonlinea ly cons ained es ima ion
p oblem in he con ex s o bo h mean squa e e o (MSE) and leas squa es e o (LSE). The
class o cons ain s emphasized we e hose wi h a null space spanned by a linea basis se
and includes all linea cons ain s and nonlinea qua.d. a ic cons ain s.
The
app oach aken
employs a cong uen ans o ma ion and maps he p oblem o one o dis ance minimiza ion
o e an app op ea e null space. Closed o m cons ained solu ions a e de i ed o
he
cases
o linea cons ain s and nonlinea quad a ic cons ain s.
1.
INTRODUCTION
The p oblem o pa ame e es ima ion subjec o
cons ain s has been s udied
o
nume ous applica ions
in signal ananysis and con ol heo y
[1].
Va ious me h-
ods ha e been employed
o
iden i y sy ems wi h linea
cons ain s
[2].
Some o he iden i ica ion me hods a e
l?ased
on ap io i s a is ical knowledge while o he em-
ploy a ini e sequence o
da a
obse a ions. This pape
add esses he cons ained mean squa ed e o (MSE)
and leas squa es e o (LSE) es ima ion p oblenis om
he
iew poin o signal space subspace, signal null
space and cons ain null space.
The null space o a cons ain unc ion is in o-
duced as a ehicle wi h which
o
sa is y he cons ained
es ima ion p oblem wi h minimal o no inc ease in es-
ima ion e o . The cons ain unc ion is in a ian o
upda es in he weigh ec o which a e es ic ed
o
he
cons ain unc ion null space. Thus,
he
cons ain
unc ion null space may be sea ched o ob ain an op-
imal weigh ec o which sa is ies he cons ain wi h
minimal penal y in es ima ion e o .
The case whe e he cons ain null space is spanned
by a linea basis is emphasised.
In
his case analy i-
cal exp essions a e de i ed o calcula e
he
elemen s o
he
op imal cons ained weigh ec o . Included in his
class o cons ain s a e linea cons ain s and nonlinea
qua.d. a ic cons ain s.
In he MSE es ima ion p oblem he e o su ace
measu e has a null space o dimension ze o
[3].
In his
p oblem, he app oach aken is
o
pe o m a cong u-
en ans o ma ion on
he
weigh ec o esul ing in
a symme ic e o su ace. Unde his ans o ma ion
he
op imal weigh ec o is ob ained ia dis ance min-
imiza ion by sea ching he cons ain null space o a
weigh ec o wi h he sho es possible dis ance
o
he
null space o he LSE su l'ace.
The LSE es ima ion p oblem
is
conside ed in he
con ex o he minimum no m cons ain
[4,5].
He e he
esul is a unique solu ion de e mined by he pseudo in-
e se o he
da a
ma ix and co esponds
o
selec ing
a pa icula membe o he subspace o he weigh
ec-
o s which in e sec only he o igin o he nullspace.
The in a ian pe o mance imposed by he span o he
null space is
used
as a e e ence in sea ching o and
selec ing an op imal LSE solu ion om a se o
com-
pe i i e subop imal ea u es.
Sea ching he nullspace is pe o med by i s de in-
ing he LSE null space basis ia singula alue decom-
posi ion (SVD) o he
da a
ma ix
[6].
These bases a e
hen
used
o de e mine he addi ional null space weigh
componen s which when added
o
he minimum no m
solu ion esul in a
o al
weigh ec o which has he
sho es dis ance om he null space o
he
nonlinea
cons ain s.
The
pape p esen s a uni ied null space app oach
o sol e
he
MSE and LSE es ima ion p oblems. An-
aly ical solu ions a e p esen ed o he case o linea ly
spanned null spaces o he cons ain and e o pe -
o mance su aces. Examples o he es ima ion p ob-
lems a e p esen ed o he nonlinea quad a ic smoo h-
ness cons ain and may be ex ended
o
quad a ic con-
s ain s in gene al.
The abo e cases o he leas mean squa ed leas
squa es es ima ion p oblems a e conside ed in
he
con-
350
ex
o
a simple ini e impulse esponse (FIR) linea
p edic o .
The
one s ep p edic o ou pu u(i) may
be
exp essed as he con olu ion sum
M
d(i) =
2:U. •u(i-
k +
1)
(1)
.1:=1
whe e M is
he
il e leng h,
w,~:
a e he il e weigh s
and
he
u(-)
a e he
ap
inpu s.
2. CONSTRAINT NULL SPACE INVARIANCE
In
he case o eal da a, cons ain s on he weigh
ec o ,
wE
R,M., may in ol e equali y
and/o
inequal-
i y ela ions. In he case
o
an equali y cons ain ela-
ion on
he
weigh ec o ,
/(w)
=
C,
he image
o
he
cons ain unc ion
/(w)
may be ec o alued wi h
C E
'R.-
11
o 1 S k
:$
M.
In
he case when an inequal-
i y cons ain ela ion is imposed such as
/(w)
:$
0,
he cons ain unc ion is aken
o
be a unc ional wi h
OE'R.
In
ei he cons ain ela ion, equali y
o
inequal-
i y,
he
null space
N( (w))
o
he
cons ain ela ion
/(w)
is a subse
o he
space
o
all possible weigh ec-
o s
R,M.
The
null space
o
he cons ain unc ion is
de ined as
he
se
N(/(w))
={wE
'RMI/(w) =
0,
0 E 'R
11
, 1
:$
k $ M}
(2)
The
cons ain unc ion
/(w)
is null space in a ian
i
/(w
+ z) =
/(w)
(3)
Vw
E 'RM and
Vz
E
N(/w).
Fu he mo e,
i
he
null
sapce
o
he
cons ain unc ion is spanned by a lin-
ea
basis,
he
cons ain is said o be null space lin-
ea ly in a ian o simply linea ly in a ian .
The
class
o
linea ly in a ian il e cons ain s includes linea and
quad a ic cons ain unc ions.
2.1
Linea Cons ain Case
The
null space linea in a iance o a linea con-
s ain on
he
weigh ec o
is
eadily p o en.
The
linea cons ain unc ion akes
he
o m
/(w)
=
Aw
whe e A is
an
M X M ma ix.
The
null sapce
o
his
linea cons ain may be exp essed as
N(A)
={wE
'RMIAw =
0}
(4)
The
linea in a iance
o
he
cons ain ollows di ec ly
om
he
p ope y
A(w
+
x)
=
Aw
Vx E
N(A)
(5)
The
dimensionali y
o
he
cons ain null space is di-
ec ly ela ed o
he
ank
o
he
cons ain ma ix by
dim{
N(A)}
= !'ank(A)
-M
The
null space
o
a linea
ans o ma ion is spanned by : ini e basis
o
( l'ank(
A)-
M) ec o s and so is a subspace
o
R,M.
The
linea con-
s ain is hus linea ly in a ian .
2.2 Quad a ic Cons ain Case
Quad a ic cons ain s on
he
weigh ec o possess
acons ain unc iono he o m (w)
=
wTQw,
whe e
Q in an M X M symme ic ma ix and
he
supe sc ip
(
)T
deno es
he
anspose ope a ion.
The
null space
o
he
quad a ic cons ain is cha ac e ized by
N(Q)
={wE
'RMiwTQw =
0,0
E
'R}
o equi alen ly
={wE
'RMIQw =
0,0
E
'R}
(6)
Thus
he
null space o he quad a ic cons ain unc-
ion has a : ini e dimensional se
o
basis ec o s. The
quad a ic cons ain unc ion also possesses
he
null
space linea in a iance p ope y since
(w+x)
=
(w+x)TQ(w+x)
=
Qw
+ 2
Qw
+ XTQx
= Qw
=
/(w)
(7)
o all
wE
R,M and x E
N(Q).
A undamen al example
o
a qua a ic cons ain
is he smoo hness
o
la ness measu e. Acco ding o
his measu e an equal coe icien il e co esponds o
a maximally ia impulse esponse. This is equi alen
o
d i ing
he
il e owa ds a sine unc ion in
he
e-
quency domain and in his con ex minimizing il e
bandwid h. Gi en a weigh ec o
w,
a measu e o i s
smoo hness is exp essed as
M
J.(w)
=
E<w•-
iii)
2
1=1
=wTQw
(8)
whe e
iii
is
he
a e age alue
o
he
weigh s and Q
is
an M X M symme ic ma ix wi h en ies
{¥
o i=}
q;J =
-1
i
·-~..
11'
o l J
(9)
The
null space o Q
is
one dimensional and spanned
by
he
M X 1 uni ec o
(10)
A maximally ia impulse esponse co esponds
o
ze o
a iance
in
he
weigh ec o which implies pe ec smoo h·
3.
I
ma
o ·
OU J
expl
whe:
o ]
ec '
ela
he,
he
c
and
wheJ
ion
he
c
in o
Oa Je
ali y
esuli
Ca Je
siona
cons
mul
aken
weigh
hen:
ec o:
su ac
j
s ain
s ain
ion 1
i s .
au oc
ss
e
p
ce
6)
.c-
~e
ill
7)
n
o
o
n
·e-
e
i S
8)
is
9)
'Y
0)
o
oo h-
I
j
j
"
I
~
1
ness and hus
w =
ci:
o some c E
'R.
(11)
3. LEAST MEAN SQUARED PERFORMANCE
Gi en
a.
desi ed esponse d(n), he leas MSE es i-
ma ion p oblem is one o de e mining he weigh
ec-
o
w which minimizes he mean squa ed alue o he
ou pu
e o . This e o , assuming eal
da. a.,
ma.y
be
exp essed
a.s
hMs
=
£[(d(n)-
d(n))2]
=
u~
-2w!' p + 2wTR
(12)
whe e £ deno es he expec a ion ope a o . The
ec-
o p
is
he c oss-co ela ion ec o be ween
he
inpu
ec o and he desi ed esponse, and R is he a.u oco -
ela ion ma ix
o he
inpu ec o u(n).
In
he case whe e no cons ain s a e imposed upon
he
weigh ec o in he p ocess o
minimizU1g
he MSE,
he op imal weigh ec o in gi en by
(13)
and he MSE has
he
o m
hMs
= JMIN +
(w+wo)TR(w
-w
-wo)
(14)
whe e JMIN =
hMs(wo).
The weigh ec o w o
is
unique, he a.u oco ela.-
ion ma ix R is o ull
ank
and posi i e de ini e. Thus
he cons ained op imiza ion p oblem
ma.y
be di ided
in o wo cases.
Oa3e
I. The null space o he cons ain
ha.s
dimension-
a.li y
ze o.
In
his case, adhe ence
o
he cons ain
esul s in
a.
di ec sac i ice in MSE.
Oa3e
11.
The null space o
he
cons ain
ha.s
dimen-
siona.li y g ea e
han
ze o. Thus, he null space o he
cons ain may be sea ched o minimize MSE while si-
mul aneously sa is ying he cons ain .
The
app oach
aken is
o
pe o m a cong uency ans o ma ion o he
weigh ec o esul ing in a symme ic MSE su ace and
hen sea ching he cons ain null space o he weigh
ec o wi h he sho es dis ance
awa.y
om
he
e o
su ace minimum.
An example o
Case
11.
is
he smoo hness con-
s ain .
The
one dimensional null space o his con-
s ain
ha.s
i as
a.
basis.
The
cong uency ans o ma-
ion esul ing
is
a.
symme ic e o su ace
i
speci ied
i s . Le V be a uni a y ma ix which diagona.lizes he
au oco ela. ion ma ix R. Then,
R=
T-
1
AT
(15)
351
whe e A
is
a.
diagonal ma ix whose diagonal en ies a e
he eigen alues o R.
The
desi ed cong uency ans-
o ma ion
ma.y
be exp essed
a.s
w =
Tow
whe e
VJ:?iT
(16)
which maps he weigh ec o w
ow.
The
p oblem
is
now
ans o med
o
a.
dis ance
min-
imiza ion p oblem. The ans o med cons ain null
space is sea ched
o
ind
he
weigh ec o colses
o
he image
o wo.
I
ca.n
be ea.dily shown
ha
he null
space componen o he is cha ac e ized by
Cop i
whe e
(17)
4. LEAST SQUARES PERFORMANCE
The leas squa es es ima ion p oblem u ilizes he
sum o e o squa es pe o mance measu e. Employing
he co a. iance me hod o windowing he inpu da a.
u(i), i =
1,
...
, N; he sum o e o squa es measu e
is
gi en by
N
Je(w ,
...
,wM) = E le(iW
(18)
i=M
whe e e(i) =
u(i)-
u(i)
Equa ion (2) may be exp essed as
(19)
Je(w) =
T
=
(b-
Aw)T(b-
Aw)
(20)
whe e
W =
(w ,
W2
1
...
1
WM)T,
(21)
= [e(M), e(M +
1),
...
, e(N)]T,
(22)
b = [u(M + 1),
u(M
+
2),
...
,
u(N
+
1)JT,
(23)
a.nd
[
u(M)
u(M-
1)
. . .
u(1)
l
u(M
+
1)
u(M)
..
. u(2)
A=
u(~)
u(N:-1)
. :.
u(N-
~
+
1)
(24)
The supe sc ip T deno es ansposi ion, w
is
he M x 1
a.p
weigh ec o ,
u(i)
is
he M x 1 inpu ec o ,
is
he
Mx1
esidual ec o , and A
is
he
(M
-N
+1)xN
da. a.
ma ix.
The leas squa es solu ion o he il e weigh s,
which minimizes Je o e he
da a
window, sa is ies he
no mal equa ion
352
(25)
I
ank(A) = M,
AAT
is nonsingula
and
he ap
weigh s a es uniquely de e mined as w =
(AAT)-
1
AT
b.
On
he
o he
hand, o ank(A) =
<M
he
nulli y
o A is nonze o and
he
leas squa es solu ion
,w,
is no
longe unique.
In
his case,
he
pseudo in e se
o
he
da a. ma ix, deno ed
AI,
cha ac e izes
he
minimum
no m
solu ion
ha
is gi en by
w=A'b
=
x:E- yx
(26)
The
o hogonal ans o ma ion ma ices Y
and
X
o
he
singula alue decomposi ion (SVD)
o
A cha ac-
e ize
he
null space,
N(A),
and
he
ange space, R(A),
o
he
da a
ma ix, espec i ely.
The
i s diagonal
en ies
o
:E
sa is y
U
~
112
~
••••
,
ITM
~
0 while
he
es
o
he
ma ix elemen s ha e ze o alues.
The
las
(M-
) + 1 columns
o
he
ma ix X o m
an
o hono -
mal basis o
N(A).
In
he
cons ained leas squa es p oblem ou cases
esul based upon p e o mance
and
cons ain nulli y.
Case
I.
The
da a. ma ix A is ull ank
and
he
con-
s ain
null spca.e has dimension ze o.
In
his
case a
di ec sac i ice
o
minimum LSE esul s
in
sa is ying
he
cons ain .
Case
II.
The
da a
ma ix A is ull ank
and
he
con-
s ain
null space dimension is g ea e
han
ze o. He e
he
null space
o
he
cons ain
may
be
sea ched so as
o
sa is y
he
cons ain
wi h
mimimum inc ease in LSE
which is analagous
o
he
LSE p oblem.
Case
Ill.
The
da a
ma ix
A is
ank
de icien
and
he
cons ain null space is dimension ze o.
I
he
con-
s ain
is elaxed,
he
null space
o
he
da a
ma ix
may
be
sea ched
o
ind
he
weigh ec o which bes sa is-
ies
he
cons ain
a
minimum LSE again analagously
o
he
MSE p oblem.
Case
IV.
The
da a.
ma ix
A is ank de icien
and
he
dimension
o
he
cons ain null space is
g ea e
han
ze o. Now
bo h
he
pe o mance measu e
and
he
con-
s ain
null spaces may
be
sea ch simul aneously
o
sa -
is y
he
cons ain
wi h
minimum LSE penal y
o
o
main ain
he
leas possible MSE while sa is ying
he
cons ain as well as possible.
Conside
Case
IV.
in
which smoo hness is
o
be
maximized wi hou sac i icing minimum LSE.
The
se
o
column ec o s X..+ ,
••.
,
XM
o
X o m an o hono -
mal basis o N(A). Mo ing a weigh ec o h ough
N(A) does
no
change
i s
LSE e o , i.e. Je(w) =
Je(w +
.6.w),
V.6.w
E N(A).
Thus
he
leas squa es
p oblem in
e ms
o
he
bases o N(A)
and
N(Q)
is:
gi en
he
minimum
no m
leas squa es weigh ec o
W,
ind
he
scala s
c,
< + ,
•..
,
aM
which minimize
M
WTOT
= L
a;x;
(27)
i= +l
I
can
be
shown
ha
he
scala s in
he
ela ion abo e
which maximize smoo hness wi hou inc easing
he
leas
squa es e o a e
(16)
and
(17)
REFERENCES
[1]
G. C. Goodwin
and
K.
S. Sin, Adap i e Fil e ing,
P edic ion
and
Con ol, P en ice-Hall, Englewood
Cli s, NJ, 1984.
[2)
T.
Mu
and
L.
G i li hs,
"A
solu ion space app oach
o
achie ing pa ially adap i e a ays,"
IEEE
In-
e na ional Cop. e ence on Acous ics, Speech and
Signal P ocess., New Yo k, NY, Ap il, 1988.
[3)
S. Konyk and M. Amin," A new class
o
nonlinea. ly
cons ained linea es ima o s,"
IEEE
In e na ional
Con e ence on Acous ics, Speech
and
Signal P o-
cess., New Yo k, NY, Ap il, 1988.
[4)
S. Konyk,
M.
Amin and
M.
Lagunas,"Leas squa es
null space a ia ional cha ac e iza ion o nonmin-
imum
no m
solu ions,"
IEEE
In e na ional Con-
e ence on Acous ics, Speech and Signal P ocess.,
Glasgow, Sco land, Ap il, 1989.
[5)
S.
Ha.ykin, Adap i e Signal P ocessing, P en ice-
Hall, Englewood Cli s, NJ, 1986.
[6)
G. Golub and C. Van Loan, Ma ix Compu a ions,
Johns
Hopkins Uni e si y P ess, 1983.
In
summa y,
he
pape
p esen ed a null space app oach
o
he
leas squa es
and
mean
squa e es ima ion p oblems. Op imal solu ions a e de i ed by sea ching
he
null spaces
associac ed wi h pe o mance e o su aces
and
cons ain unc ions o weigh ec o s wi h
minimal dis ances
o
hese spaces.
In
he
MSE es ima ion p oblem only
he
null space
o
he
cons ain
was
sea ched, while
in
he
LSE es ima ion p oblem
bo h
he
signal null space and
he
cons ain null space we e sea ched simul aneously
o
ob ain
he
op imal weigh ec o .
Analy ical esul s we e de i ed o
he
case whe e each
o
he
null spaces
was
spanned by
a.
linea basis which includes
he
class
o
all nonlinea
quad a ic
cons ain s.
SIGNAL
L.
To"ll
@Else~
1.
n
The
1
ha in
ion
densi
in
se
a lon
a ic
o
gE
nals
some
as
o:
cien
an:
ed.
some1
pone1
wo
'
The
1
he
'
he
l
pe .
2.
The
he
si
nal
•
Le
sio i<
co a:
sen '
ollo
whe '
ion
a e
[0,
~
The
he