Transcript ica-mud

ICA-based Blind and Group-Blind
Multiuser Detection
Independent Component Analysis(ICA)
What is Independence?
p ( yi y j )  p ( yi ) p ( y j ),
for i  j
Definition
Independence is much stronger than Uncorrelated.
E{ yi y j }  E{ yi }E{ y j }  0,
for i  j
E{g ( yi ) f ( y j )}  E{g ( yi )}E{ f ( y j )}  0,
for i  j
Uncorrelated
Independence
What is ICA ?
Independent Component Analysis (ICA) is an analysis technique
where the goal is to represent a set of random variables as a linear
transformation of statistically independent component variables.
Independent Component Analysis(ICA)
ICA Model (Noise-free)
x  As
Unknown Mixing Matrix:
Unknown Random Vector:
si , s j
M N
s  [ s1 , s2 , sn ]T
are assumed independent
ICA Model (Noise)
x  As  n
Noise
ICA Goal: Find a Matrix W which recovers
s  y  Wx
ICA: Principles and Measures
Independence

Nongaussian:
yi  wi x  wi As  zT s
T
T
Want yi to be one independent component
Central Limit Theorem:
Minimize Gaussianity of
sj
yi
Differential entropy:
Measures of Nongaussian:
1. Kurtosis:
Kurt ( y)  E{ y 4 }  3E ({ y 2 })2
2. Negentropy and Approximation:
J ( y )  H ( y gauss )  H ( y ) 
H ( y )    f ( y ) log f ( y )dy
1
1
E{ y 3 } 
Kurt ( y ) 2
12
48
ICA: Principles and Measures
Measures of Nongaussian: (continued)
3. Mutual information
I ( y1, y2, ... ym ) 
y  Wx
 H ( y )  H ( y)
i
i
I ( y1, y2, ... ym ) 
 H ( y )  H ( x)  log det W
i
i
4. Kullback-Leibler divergence:
 ( f1, f 2 ) 

f1 ( y ) log(
f 1( y )
)
f 2 ( y)
Real density
Factorized density
Kullback-Leibler divergence can be considered as a kind of a distance
between the two probability densities, though it is not a real distance measure
because it is not symmetric
Principle Component Analysis
Principle Component Analysis
1. Goal is to identify a few variables that explain all (or nearly all) of the total
variance.
2. Intended to narrow number of variables down to only those that are of
importance.
3. “Faithful” in the Mean-Square sense. Faithful
Interesting!

Synchronous CDMA
Received signal
K
r (t )   bk Ak sk (t )  n(t ),t  [0, T ]
k 1
where
–
–
–
–
bk  {-1,+1} is the k’th user’s transmitted bit.
hk is the k’th user’s channel coefficient
sk(t) is the k’th user’s waveform (code or PN sequence)
n(t) is additive, white Gaussian noise.
Blind Multi-user Detection
Multiple Access Interference (MAI)
– Due to non-orthogonal of codes
– Caused by channel dispersion
What does “Blind” Mean?
– Only the Interested user’s
Spreading code is Known to the
receiver
– Channel is Unknown
Group-Blind MUD

Multiple-Access Interference
(MAI)
– Intra-cell interference:
users in same cell as
desired user
– Inter-cell interference:
users from other cells
– Inter-cell interference 1/3
of total interference
Inter-cell MAI
Intra-cell MAI
Blind Multi-User Detection
Non-Blind multi-user detection
– Codes of all users known
– Cancels only intracell
interference
Blind multi-user detection
– Only code of desired user
known
– Cancels both intra- and
inter-cell interference
Group-blind MUD




K users with known codes
K users with unknown codes
Signal is sampled at chip rate
(from matched filter)
Cancels both intra- and inter-cell
interference
Synchronous Signal Model
Uniform Received Model
K
K
k 1
j 1
r (t )   b k Ak s k (t )   b j A j s j (t ) v(t ),t  [0, T ]
Chip Matched Filter:
chip1 chip2 chip3 …
Discrete Model
Spreading Gain of
K
K
k 1
j 1
sk
is N
r[i ]   b k [i ] Ak s k   b j [i ] A j s j v[i ]
 S Ab[i]  S Ab[i ]  v[i ]  SAb[i ]  v[i ]  Hb[i ]  v[i ]
Synchronous!
r  H b  H b  v  Hb  v
Total Number of Users:
K KK
Sub-space Concept
Auto-correlation Matrix of Received Data
R  E ( rr H )  HH
H
  2I
Auto-correlation Matrix (EVD)
H



0
U


s
H
H
2
H
s
R  UU  U s U n 

U

U


U
U
s s s
n n
2  H 
0

I
U

 n 
 s  diag( 1 ,..., K ),i   2
span(U s )  span( H )
FastICA & Challenges in CDMA
Fixed-point algorithm for ICA (FastICA)

Based on the Kurtosis minimization and maximization

Two advantages:
1. Neural network learning rule into a simple fixed-point iteration;
2. Fast convergence speed: Cubic
See Handout for Detail
Ambiguities:

Variance: Undetermined variances (energies) of the independent

components;
Order: Undetermined order of the independent components.
ICA in CDMA:Hints
Hints:
ICA Model:
y  1/ 2U H r
Data whitening
y  1/ 2U H Hb  1/ 2U H v
G
Ignore noise
E{ yy H }  E{GbbH G H }  GG H  I
wkICA  G1k
( wkICA ) H Gb  bk
( wkICA ) H y  bk
Blind MMSE Solution
wkMMSE  arg min E{( bk  wkH r ) 2 }
wk
wkMMSE  R 1 H 1k  U1U H H 1k
Two Questions
Question No.1
x  As  v
si , s j : are Independent.
r  Hb  v
bi , b j
: Not only Independent; but also
+1or-1with with equal probability!
Question No.2

FastICA: Many Local local minima or maxima;
MMSE ICA: Near MMSE local minima or maxima

Finding a tradeoff between two objective functions.

Can we find a better local minima or maxima which gives
better performance by starting from other initial points?
ICA-based Blind Detectors

Question No.1
Lemma:
For a BPSK Synchronous DS-CDMA
system,the maximization of Approximated
Negentroy using high-order moments is same
as the minimization of the Kurtosis.
See Handout for Proof
More Interesting Result?
ICA-based Blind Detectors
Question No.2
MMSEICA Detector:
y  1/ 2U H r
wkMMSEICA  U1/ 2 H 1k
Zero-Forcing ICA Detector:
y s  s
ZFICA
k
w
1/ 2
H
Us r
 (U s  I K ) s
1/ 2
H1k
Performance of Blind Detector
Performance of Blind Detector
Summary for Blind Detectors
Advantages
1. ICA-based blind detectors have better performance than the
subspace detectors in high SNRs.
2. ZFICA Detector has better performance than MMSEICA Detector.
Reduced complexity and robust to estimated length.
3. ICA-based blind detectors are free to BER floor.
4. When system is high loaded the performance of ZFICA
is close the non-blind MMSE detector.
Disadvantages
1. ZFICA Detector needs know K
2. ICA-based blind detectors:less flexibility to estimated length.
Group-blind MUD Detector
What is the Magic?
Make use of the signature waveforms of all known users
suppress the intra-cell interference,while blindly suppressing
the inter-cell interference.
Group-blind Zero-Forcing Detector
wkGZF  U s ( s   2 I ) 1U sH H [ HU s ( s   2 I ) 1U sH H ]11k
ICA-based group-blind detector
1. Non-blind MMSE (Partial MMSE) to eliminate the
interference from the intra-cell users
W
PMMSE
H
 (H H   I ) H
2
1
H
2. Zero-Forcing ICA Detector based on output of Partial MMSE
Performance of Group-blind Detectors
GroupBlind-ICA Detectors with 100 Symbols (12 incell,8 outcell)
0
10
GroupBlind ZF
Partial MMSE
Blind ZFICA
GroupBlindZFICA
-1
BER
10
-2
10
-3
10
6
7
8
9
10
11
12
SNR Eb/No (dB)
13
14
15
16
Performance of Group-blind Detectors
GroupBlind-ICA Detectors with 200 Symbols (12 incell,8 outcell)
0
10
GroupBlind ZF
Partial MMSE
Blind ZFICA
GroupBlindZFICA
-1
BER
10
-2
10
-3
10
-4
10
6
7
8
9
10
11
12
SNR Eb/No (dB)
13
14
15
16
Summary for Group-blind Detectors
1. Group-blind ZFICA detector has better performance than
group- blind zero-forcing subspace detector.
2. Group-blind ZFICA detector Worse performance than the totally
blind ZFICA method.
Partial MMSE Destroyed the Independence of
desired random variables. Independent >
Interference!!
Reference
References
[1] J.Joutsensal and T.Ristaniemi,”Blind Multi-User Detection by Fast Fixed Point Algorithm
without Prior Knowledge of Symbol-Level Timing”, Proc. IEEE Signal Processing Workshop on
Higher Order Statistics Ceasarea,Israel, June 1999,pp.305-308.
[2] T.Ristaniemi and J.Joutsensal, ”Advanced ICA-Based Receivers for DS-CDMA Systems”,
Proc. 11th IEEE International Symposium on Personal, Indoor, and Mobile Radio
Communications, London, September 18-21, 2000, pp.276-281.
[3] T.Ristaniemi,”Synchronization and blind signal processing in CDMA
systems”,Doctoral Thesis,University of Jyv¨askyl¨a, Jyv¨askyl¨a Studies in Computing,
August 2000.
[4] X.Wang and A.Høst-Madsen, ”Group-blind multiuser detection for uplink CDMA”,
IEEE Journal on Selec. Areas in Commun, vol. 17, No. 11, Nov. 1999.
[5] X. Wang and H.V. Poor, ”Blind Equalization and Multiuser Detection in Dis-persive
CDMA Channels”, IEEE Transactions on Communications, vol. 46, no. 1, pp. 91-103,
January 1998.
[6] P. Comon, ”Independent Component Analysis, A new Concept?”, Signal processing,
Vol.36, no.3, Special issue on High-Order Statistics, Apr. 1994.
Reference
References
[7] A.Hyv¨arinen and E.Oja, ”A Fast Fixed-Point Algorithm for Independent Component
Analysis”, Neural Computation, 9:1483-1492, 1997.
[8] A.Hyv¨arinen, ”Fast and Robust Fixed-Point Algorithm for Independent Component
Analysis”, IEEE Trans. on Neural Networks, 1999.
[9] A.Hyv¨arinen, ”Survey on Independent Component Analysis”, Neural Com-puting Systems,
2:94-128, 1999.
[10] S. Verdu, ”Multiuser Detection. Cambridge”, UK: Cambridge Univ. Press, 1998.