Algoritmos Rápidos no domínio do tempo para ICA Convolutivo

Resumo - Esta carta apresenta novos métodos de separação cega para misturas convolutivas de Média Móvel (MA) de processos independentes. Elas consistem em extensões do domínio do tempo dos algoritmos FastICA desenvolvidos por Hyvarinen e Oja para as misturas instantâneas. Elas executam uma esferização convolutiva a fim de usar parâmetros livres de algoritmos livres de ponto fixo associados critérios naõ-gaussianicos de curtose ou negentropia para estimar os processos de inovação de fonte. Provamos a relevância dessa abordagem, mapeando as misturas em mapeamentos lineares instantâneos. Os resultados do teste são apresentados para sinais artificiais coloridos e sinais de fala.

Termos de indexação - Misturas Convolutivas, algoritmos de ponto fixo, análises de componentes independentes (ICA), sinais não-gaussianos

Separação Cega de Fontes (BSS) consiste em estimar uma seleção de sinais N de fontes não-observáveis de P misturas observáveis dessas fontes onde os

parâmetros de misturas são desconhecidos. Denotemos por o

vetor de fontes e por o vetor das observações. Nós consideramos misturas convolutivas definidas por uma seleção de filtros desconhecidos com respostas ao impulso hij(n) onde i =1,..,P e j = 1,...,N. A relação entre as fontes e as observações pode ser expressa no domínio do tempo como:

A relação geral então lida no domínio Z:

Onde X(z) e S(z) são, respectivamente, a transformada Z de X(n) e S(n), e P x N

matriz H(z) consiste da função transferência dos filtros de mistura.Nesse artigo, cada fonte Sj(n) é assumida sendo expressa no domínio Z como:

Onde F(z) corresponde a um filtro, e Uj(z) é a transformada z de um processo uj(n),

na qual é o processo de inovação de sj(n). Denotando nós então podemos expressar a mistura (2) como:

Onde Nós podemos fazer as seguintes suposições acerca do modelo de mistura.

O processo é real-estimado, média zero, independente e identicamente distribuído (i.i.d.) e espacialmente independente, isto é, suas componentes uj(n) são estaticamente independentes uma de cada outra mas não necessariamente tem a mesma distribuição. Nós também assumimos que, na maioria, uma dessas componentes é gaussiana.

O filtro de matrizes F(z), H(z), e G(z) são causais, tem resposta ao impulso finita (FIR), e não singular. Note que sistemas com resposta ao impulso

infinita (IIR) podem também ser aproximados pelo modelo FIR equivalente (de ordem alta).

O objetivo da convolução BSS é tipicamente estimar a contribuição de todas as fontes em cada observação, isto é, Hij(z) . Sj(z). Nos métodos baseados em deflação tais como [1], isso é alcançado usando o seguinte procedimento.

1. Extrair o processo de inovação Uj(n) de uma fonte Sj(n) das observações.2. Identificar P filtros coloridos e aplicando eles a Uj(n) a fim de recuperar as

contribuições de Sj(n) em cada observação, isto é, Hij(z) . Sj(z).3. Subtraia essas contribuições de todas as observações.4. Selecione volte para o passo 1) a fim de subtrair da outra

fonte.

Nós aqui consideramos o método BSS no domínio do tempo, na qual se usa a não-gaussianidade como critério para realizar o primeiro passo dos procedimentos acima e nos quais são, além disso, baseados na análise de componentes independentes (ICA) [2]. Na próxima seção nós analisamos os princípios e limitações dos métodos existentes, e propomos uma aproximação para estender eles assim como para obter o método de rápida convergência curtótica atualmente faltante e, métodos negentrópicos para misturas convolutivas. O desempenho experimental dos métodos propostos é apresentado na seção III, e conclusões são feitas dessa investigação na seção IV.

II. Análise e Extensão dos Métodos BSS baseado na Não-Gaussianidade

A. Aproximações relatadas anteriormenteDelfosse e Loubaton [3] propuseram o primeiro método curtotico BSS baseado na deflação para misturas lineares instantâneas, onde os filtros Hij(z) são repostos por coeficientes escalares. Esse método primeiro consiste em calcular de uma versão esférica v(n) de um vetor observação x(n), isto é, a seleção de combinações lineares dessas observações compostas de sinais que são mutualmente descorrelacionados no tempo ‘n’ e que têm variâncias unitárias. O primeiro sinal de saída é então calculado como uma combinação linear das observações esféricas, com um vetor de coeficiente normalizado ‘w’ selecionado assim como para maximizar o quadrado (ou o valor absoluto) da curtose não-normalizada de y(n) definida por

para um sinal de média zero. Delfosse e Loubaton provaram em [3] que a máxima local desse critério corresponde a pontos de separação. Eles usaram um método como gradiente para maximizar esse critério. Isso requer uma seleção de um ganho adequado de adaptação e rendimentos de convergência lenta. Hyvarinen e Oja resolveram esse problema introduzindo um algoritmo de ponto fixo para otimizar o critério acima [2]. Uma diferente aproximação foi proposta por Tugnait para misturas convolutivas [1]. Isso opera diretamente nas observações, isto é, sem esferiliza-las primeiros, mas então usar o valor absoluto da kurtose normalizada do sinal de saída y(n), isto é, como o critério de separação. Tugnait provou que os pontos de separação correspondem ao máximo local desse critério quando se recombina as observações com filtros infinitos de dupla extração. Ele propôs utilizar esse critério usando uma aproximação baseada em gradiente, nas quais temos novamente rendimentos de convergência lenta. Os testes realizados pela nossa equipe [4] mostraram que, mesmo quando usamos esquema de optimização Newtoniana, a convergência permanece lenta, especialmente para filtros de mistura de alta-ordem.Esse artigo, portanto, objetiva o preenchimento de lacunas resultantes das aproximações acima, isto é, ao introduzir métodos curtoticos e negentrópicos de rápida convergência para misturas convolutivas. Para finalizar, nós investigamos primeiro como estender para misturas convolutivas a aproximação baseada na esferização e optimização de ponto

fixo de curtoses não normalizadas que tem sido proposto para misturas instantâneas.

B. Novos Métodos para extração de um Processo de Inovação Todos os métodos acima requerem uma normalização, como a curtose não normalizada de y(n) tende ao infinito, quando a potência de y(n) tende ao infinito. Na aproximação de Tugnait, o critério por si só é normalizado como o método que consiste na estimativa dos processos de inovação uj(n) até um fator de atraso e escala por maximizar o valor absoluto de uma curtose normalizada de uma combinação convolutiva de observações definidas como:

Onde são P filtros FIR não-causais na prática. Ao invés disso, as duas aproximações lineares instantâneas mencionadas na subseção anterior usa curtose não normalizada e são baseadas na normalização da potência de y(n). Isso resulta da etapa de esferização

dessas aproximações, na qual rende assim que a seleção

w com ||w||2 = 1 garante que .Nós aqui estendemos esse método para mistura convolutivas. Ao final, o primeiro passo da nossa aproximação realiza a “esferizaçao convolutiva” das observações, definida como segue. Em qualquer tempo n, nós consideramos o vetor coluna

Que contém M = (2R + 1) entradas. Nós derivamos as M-entradas do vetor

coluna definida como

Onde B é uma matriz MxM escolhida tal que:

Com respeito a x~(n), a operação (7) pode portanto ser considerada como esferizaçao convencional, o que consiste da principal análise de componentes e normalização. Agora, com respeito à observação original xi(n), isso pode ser interpretado diferentemente. Certamente (6) e (7) mostram que os sinais xi’(n) são misturas convolutivas de xi(n). Equação (8) então quer dizer que o sinal xi’(n) são criados para ter variâncias unitárias e para ter descorrelação mútua, o que pode ser visto como um branqueamento espaço temporal e normalização das observações xi(n). Vamos denotar por y(n) o sinal extraído:

Onde w é uma M-entrada vetor coluna estendido de coeficientes de extração wm que, juntos com (7), rende uma combinação convolutiva y(n) das

observações. A potência de y(n) lê . Por restrição xi’(n) assim como conhecer (8), nós temos

Portanto:

Nosso método então consiste em maximizar o valor absoluto da curtose não

normalizada de y(n) definida por (9) sob o restrição O apêndice mostra que esse critério nos extrai uma estimativa el(n) de um processo de inovação de fonte “atrasada” e “escalada” sob algumas condições.Além disso, algoritmos poderosos para realizar uma otimização forçada do valor absoluto das curtoses de y(n) podem ser então diretamente derivadas daquelas reportadas anteriormente para misturas lineares instantâneas, porque o apêndice mostra que misturas convolutivas x~(n) estudadas nesse artigo podem ser reformuladas como misturas instantâneas em determinadas condições. Especialmente, nós propomos como uma extensão de [2] o seguinte algoritmo ICA curtótico convolutivo de ponto-fixo rápido baseado no nosso vetor w modificado.

Inicialize w com um valor wo usando as aproximações apropriadas abaixo.

Repita os seguintes passos 1) e 2) até convergência

O valor wo de w mencionado inicialmente acima, pode ser selecionado aleatoriamente. Uma aproximação melhorada pode ser obtida tomando vantagem da relação que existe entre nosso vetor w e os coeficientes dos filtros FIR da aproximação de Tugnait definida em (5). Certamente consideraremos as colunas de nossa matriz de esferização B e o índice delas como:

Baseado em (6) e (7). Usando (7), o sinal (9) extraído no nosso método lê:

Identificando essa expressão com o sinal de saída (5) na aproximação de Tugnait, temos:

E portanto:

Onde o vetor fila K consiste da resposta ao impulso dos coeficientes dos filtros k1(n) a kp(n). Essa relação nos deixa inicializar nosso vetor w como no método de

Tugnait, isto é, com filtros unitários assim que y(n) é a soma de todas as observações xp(n). Que corresponde a K=Ko definido como

Equação (15) então rende Essa inicialização de w proveu um melhor resultado experimental que uma aleatoriedade e é usado na seção III.Para misturas instantâneas, ao invés de usar a curtose, outra função contraste baseada na negentropia foi proposta por Hyvarinen para estimar a não-gaussianidade [5]. Isso tem mostrado render melhor robustez e mais baixa variância que a curtose aproximada. Em particular, isso é mais robusto para valores extremos que critério curtótico, na qual envolve momento de quarta ordem, cuja estimativa é mais sensível a discrepâncias (outliers). Além disso, um rápido e confiável algoritmo de ponto fixo foi também desenvolvido por Hyvarinen para esse tipo de função. Nós estendemos esse algoritmo negentrópico para mistura convolutivas da mesma forma como a aproximação curtótica acima, usando a seguinte fórmula de adaptação ao invés de (11) em cada iteração:

Onde g e g’ são a primeira e segunda derivada da função contraste G que é usada para estimativa da negentropia.O algoritmo curtótico proposto pode ser otimizado em termos de processamento de tempo para computar a expectativa em (11). Certamente, (11) requer a realização de um produto vetor matriz para cada índice de amostra n a fim de

computar a soma dos termos resultantes para estimativa da esperança. Por computar o vetor uma vez para iteração considerada do algoritmo e por repor x’ por na atualização (11), nós obtemos:

Por isso nós computados somente dois produtos vetor matriz, para estimar a esperança, isto é, um em e um em (18). O mesmo princípio aplicado para o algoritmo negentrópico (17).

C. Métodos BSS Globais PropostosA etapa de extração acima prove uma estimativa el(n) de um processo de inovação de fonte até um fator de escala e atraso, na qual nós depois colorimos para obter cada contribuição de fonte lth....na observação kth...xk(n). Isso pode

ser feito por calcular o filtro colorido não-causal que faz

os sinais serem mais perto de xk(n) no sentido da raiz quadrada média [4]. Isso é aqui alcançado por filtros Wieners não-causais [6], cujo coeficientes de resposta ao impulso formam vetor ckl definido por:

Onde Rel é a matriz de autocorrelação do sinal el(n) e é o vetor de correlação cruzada dos sinais el(n) e xk(n). Note que a matriz de autocorrelação tem uma estrutura Toepliz altamente regular e existem diversos métodos eficientes [6] para resolver a equação da matriz linear (19).

Depois de subtrair as contribuições de todas as observações, nós obtemos outra configuração de mistura com N-1 fontes. O primeiro passo deve então ser iterativo como explicado na seção I para extrair o processo de inovação da outra fonte.

III. RESULTADOS EXPERIMENTAIS

Nessa seção, nós ilustramos o desempenho de nossos métodos em vários exemplos. Esses algoritmos são primeiro testados para P=2 misturas convolutivas de N=2 sinais artificiais coloridos contendo 100.000 amostras. Os processos de inovação uj(n) têm distribuições uniformes. Para esse tipo de sinal, a curtose acabou sendo o melhor critério de otimização, como comparado com a negentropia, e é usado abaixo. Fig 1(a) mostra o resultado de saída das taxas sinal-interferência (SIRs), dependendo da ordem do modelo Q que nós definimos como a soma das ordens das misturas e filtros de coloração de inovação Hij(z) e

Fj(z). Para cada fonte extraída, essa SIR é a média sobre as duas contribuições da estimativa de fonte. Para cada valor de Q, 100 simulações Monte Carlo foram feitas variando a mistura e os coeficientes dos filtros de coloração de inovação com uma distribuição uniforme, e os resultados médios e desvios padrões das SIRs foram computados. A ordem de R em (6) foi selecionada para R=Q, uma vez que os testes provaram que isso gera um bom trade-off (“perde e ganha”) entre o desempenho (SIR) e custo computacional.

Na segunda série dos experimentos, nós testamos nosso algoritmo no caso indeterminado N=3 e P=2, quando os dois sinais observados contém “fonte de ruído” branca gaussiana em adição as duas fontes acima de interesse. Nós fixamos a ordem do modelo em Q=20. Por variar a potência da fonte de ruído e assim a taxa sinal-ruído (SNR) nas observações, nós investigamos a robustez da estimativa da matriz mistura para ruído. Ao final, nós computamos as SIRs das duas fontes estimadas de interesse nas quais nós cancelamos as contribuições das fontes de ruído. Fig 1(b) mostra que o nosso método é bastante robusto como SIRs permanecer superior a 10 dB para SNRs até 8 dB. Para N=P=2, nós também comparamos o tempo de processamento de nosso método com a versão modificada do algoritmo de Tugnait introduzido em [4], na qual já alcança-se velocidade mais alta que a aproximação de Tugnait por usar um algoritmo de Newton modificado. Nós variamos a ordem do modelo Q entre 0 a 30 para fontes contendo T=10.000 amostras ( T>10000 ou Q> 30 leva a inaceitável alta de processamento de tempo para 100 execuções de aproximação de Tugnait-Newton). O resultado na Fig. (1c) representa o tempo da etapa de extração de inovação, na qual está longe do maior tempo consumido. Isso mostra que nosso método é 100 vezes mais rápido que Tugnait-Newton. Em acréscimo, isso rende ligeiramente SIRs mais altas, isto é, cerca de 0.5dB. A próxima série de experimentos foi carregada com duas fontes de fala amostradas em 20kHz durante 5s. Como na primeira seleção dos experimentos, nós variamos a ordem dos filtros de mistura Hij(z), e nós novamente realizamos 100 experimentos para cada ordem de filtro. Dessa vez, nós resolvemos realizar a etapa de extração de inovação em 20.000 janela de amostras onde os sinais são quase estacionários e para estimar as SIRs nos sinais gerais. Para esses sinais de áudio, o critério de otimização negentropico revela render um melhor desempenho, provavelmente por causa da suas distribuições de cauda [5]. Os resultados na Fig. 1(d) mostram que as médias SIRs estão entre 11 e 7 dB, na qual é 4dB mais baixa que os 100.000 amostras de sinais estacionários acima. Isso resulta de 20.000 janelas de amostras, na qual rende ligeiramente desempenho mais baixo para sinais artificiais, e do processo de modelo de média móvel (MA), na qual é somente relevante fontes de voz. De qualquer forma, isso rende significante melhora de qualidade percentual. Nós também testamos nosso algoritmo negentropico com filtros misturados de 64-th ordem real medidos nos ouvidos de uma cabeça de manequim [7] e com R=64, R´=300. Nós selecionamos respostas ao impulso associadas com fontes positivas definidas por 80 e 120 graus de angulação na relação para a cabeça do manequim. Usando novamente os dois sinais de fala acima, a média de saída SIRs foram 9.1dB para a primeira fonte e 6.9dB para a segunda fonte. Esse filtros reais, portanto rendem quase o mesmo desempenho que os 64-th de ordem artificial considerados na Fig. 1(d).

APENDICE – RELEVANCIA DO CRITÉRIO CONSIDERADO

As P observações consideradas xi(n) são expressas com respeito a N processos de inovação uj(n) de acordo com (4). Eles são, além disso, processos causais desses filtros de misturas de Q-th ordem. Agora considere o vetor x~(n) definido em (6) e composto por observações atrasadas. A análise provida em (8) implica que se

Onde L=(2R+1) é o número de defasagens, então x(n) pode também ser interpretado como uma seleção de misturas lineares instantâneas de fontes correspondentes, na qual são versões atrasadas e fator de escala dos processos de inovação uj(n), com ao menos muitas observações como fontes. Além disso, se (20) é conhecido, a investigação para misturas instantâneas providas em (3) prova rigorosamente que, por maximização do valor absoluto da curtose não-normalizada do sinal yn(n) definido em (9) sob constrangimento (10), nós extraímos um

processo de inovação atrasado e com fator de escala cuja estimativa prática é denotada el(n) a seguir.Se (20) não é conhecido, o problema BSS reformulado instantâneo não é determinado, isto é, isso envolve menos observações que fontes (note que é especialmente o caso quando P=N). Algumas aproximações são então necessárias. Entretanto, quando a taxa associada a (20) tende a 1 ( que é o caso quando P=N e L é largo), um processo de inovação atrasado e com fator de escala pode ainda ser precisamente estimado como combinação linear de observações disponíveis cujas curtose não normalizada absoluta é máxima sob constrangimento em (10).