A “projeção aleatória”, estritamente falando, não é uma projeção?

10

As implementações atuais do algoritmo de projeção aleatória reduzem a dimensionalidade das amostras de dados, mapeando-as de para usando uma matriz de projeção cujas entradas são iid de uma distribuição adequada (por exemplo, de ): $\mathbb R^d$ $\mathbb R^k$ $d\times k$ $R$ $\mathcal N(0,1)$

$x^\prime = \frac{1}{\sqrt k}xR$

Convenientemente, existem provas teóricas mostrando que esse mapeamento preserva aproximadamente distâncias aos pares.

No entanto, recentemente encontrei essas notas em que o autor afirma que esse mapeamento com uma matriz aleatória não é uma projeção no sentido algébrico linear estrito da palavra (página 6). Pelas explicações dadas, isso ocorre porque as colunas de não são estritamente ortogonais quando suas entradas são escolhidas independentemente de . Portanto, versões anteriores do RP, nas quais a ortogonalidade das colunas de foi aplicada, podem ser consideradas como uma projeção. $R$ $\mathcal N(0,1)$ $R$

Você pode fornecer uma explicação mais detalhada de (1) qual é a definição de uma projeção nesse sentido estrito e (2) por que RP não é uma projeção sob essa definição ?.

terminology dimensionality-reduction linear-algebra random-projection Daniel López
fonte

11

Você pode encontrar respostas para (1) pesquisando em nosso site . A asserção (2) é imediata, porque se as colunas fossem sempre ortogonais, suas entradas não poderiam ser independentes.

whuber

4

Qual é a definição de uma projeção nesse sentido estrito (algébrico linear) (da palavra)

https://en.wikipedia.org/wiki/Projection_(linear_algebra)

Em álgebra linear e análise funcional, uma projecção é uma transformação linear $P$ a partir de um espaço vectorial a si mesmo de modo a que $P^2 = P$ . Ou seja, sempre que $P$ é aplicado duas vezes a qualquer valor, obtém o mesmo resultado como se tivesse sido aplicado uma vez (idempotente).

Para projeção ortogonal ou vetorial, você tem esse

https://en.wikipedia.org/wiki/Projection_(linear_algebra)

Uma projeção ortogonal é uma projeção para a qual o intervalo U e o espaço nulo V são subespaços ortogonais.
Por que RP não é uma projeção sob essa definição?

Michael Mahoney escreve em suas notas de aula que depende de como o PR é construído , se o PR é ou não uma projeção no sentido algébrico linear tradicional. Isso ele faz nos terceiro e quarto pontos:

Terceiro, se os vetores aleatórios fossem exatamente ortogonais (como realmente eram nas construções JL originais), teríamos que a projeção JL fosse uma projeção ortogonal

...

mas, embora isso seja falso para Gaussianos, $\lbrace \pm \rbrace$ variáveis aleatórias e a maioria das outras construções, pode-se provar que os vetores resultantes têm aproximadamente o comprimento unitário e aproximadamente ortogonais

...

isso é "bom o suficiente".

Portanto, você poderia fazer, principalmente, a projeção aleatória com uma construção diferente, limitada a matrizes ortogonais (embora não seja necessária). Veja, por exemplo, o trabalho original:

Johnson, William B. e Joram Lindenstrauss. "Extensões de mapeamentos de Lipschitz em um espaço de Hilbert." Matemática contemporânea 26.189-206 (1984): 1.

... se alguém escolher aleatoriamente uma classificação $k$ projeção ortogonal em $l_2^n$

...

Para tornar isso preciso, deixamos $Q$ ser a projeção nas primeiras coordenadas $k$ de $l_2^n$ e deixamos que $\sigma$ seja a medida de Haar normalizada em $O(n)$ , o grupo ortogonal em $l_2^n$ . Em seguida, a variável aleatória
$f : (O (n), σ) \to L (l_{2}^{n})$ $f: (O(n), \sigma) \to L(l_2^n)$ definida por $f (u) = U^{⋆} Q U$ $f(u) = U^\star Q U$ determina a noção de uma " projeção de classificação aleatória $k$ ".

A entrada da Wikipedia descreve a projeção aleatória dessa maneira (o mesmo é mencionado nas notas de aula nas páginas 10 e 11)

https://en.wikipedia.org/wiki/Random_projection#Gaussian_random_projection

A primeira linha é um vetor de unidade aleatória escolhido uniformemente de $S^{d − 1}$ . A segunda linha é um vetor de unidade aleatória do espaço ortogonal à primeira linha, a terceira linha é um vetor de unidade aleatória do espaço ortogonal às duas primeiras linhas e assim por diante.

Mas você geralmente não obtém essa ortogonalidade quando pega todas as entradas da matriz nas variáveis aleatórias e independentes da matriz com uma distribuição normal (como Whuber mencionou em seu comentário com uma conseqüência muito simples "se as colunas fossem sempre ortogonais, suas entradas poderiam não seja independente ").

A matriz de $R$ e o produto, no caso de colunas ortonormais, pode ser vista como uma projecção, pois refere-se a uma matriz de projecção $P = R^TR$ . Isso é um pouco o mesmo que ver a regressão dos mínimos quadrados comuns como uma projeção. O produto $b = R^T x$ não é a projeção, mas fornece uma coordenada em um vetor base diferente. A projecção 'real' é $x' = Rb = R^TRx$ , e a matriz de projecção é $R^TR$ .

A matriz de projecção $P=R^TR$ necessita de ser o operador identidade no subespaço $U$ que é a gama da projecção (ver as propriedades mencionadas na página Wikipedia). Ou, diferentemente, ele precisa ter os autovalores 1 e 0, de modo que o subespaço para o qual é a matriz de identidade seja o intervalo dos vetores próprios associados aos autovalores 1. Com entradas de matriz aleatórias, você não obterá essa propriedade. Este é o segundo ponto nas notas da aula

... parece "uma matriz ortogonal de várias maneiras ... o $range(P^T P)$ é um subespaço uniformemente distribuído ... mas os valores próprios não estão em $\lbrace 0, 1 \rbrace$ .

^{note que nesta citação a matriz $P$ se refere à matriz $R$ na pergunta e não à matriz de projeção $P = R^TR$ que está implícita na matriz $R$}

Portanto, a projeção aleatória por diferentes construções, como o uso de entradas aleatórias na matriz, não é exatamente igual a uma projeção ortogonal. Mas é computacionalmente mais simples e, de acordo com Michael Mahoney, é "bom o suficiente".

Sextus Empiricus
fonte

11

Obrigado pela sua resposta, acho que vai na mesma direção que a que dei acima. Só para esclarecer eu acho que você deve indicar que

. Em seguida, como se explica, se as entradas de

são iid de

que não pode garantir que

ou que

tem valores próprios em

. Por outro lado, se as colunas de

P = R R^{T}

$P = RR^T$

R \in R^{d \times k}

$R\in\mathbb R^{d\times k}$

N (0, 1)

$\mathcal N(0,1)$

P^{2} = P

$P^2 = P$

P

$P$

{0, 1}

$\{0,1\}$

R

$R$ são ortonormais, ambas as condições são cumpridas. Mas é fundamental indicar que a projeção é

, e não

sozinho!

R R^{T}

$RR^T$

R

$R$

Daniel López

11

@ DanielLópez Eu atualizei.

Sextus Empiricus

6

Isso mesmo: "projeção aleatória" não é estritamente uma projeção.

Projecção está claramente um objecto matemático definido: https://en.wikipedia.org/wiki/Projection_(linear_algebra) - é um operador idempotentent linear, ou seja, linear operador $P$ tal que $P^2 = P$ . Aplicar uma projeção duas vezes é o mesmo que aplicá-la apenas uma vez, porque depois que um ponto é projetado em um subespaço, ele deve permanecer lá se for projetado novamente. Não há nada sobre ortogonalidade nesta definição; de fato, uma projeção pode ser oblíqua (veja Wikipedia).

Observe que apenas matrizes quadradas podem representar "projeções" nesse sentido. "Projeção aleatória" usa uma matriz $d\times k$ aleatória $R$ com $k\ll d$ , portanto, não pode ser uma projeção no sentido da definição acima.

Mesmo se você tornar as colunas de $R$ ortonormais (por exemplo, aplicando o processo de Gram-Schmidt), esse argumento ainda será aplicado. Alguém recentemente fez esta pergunta sobre PCA: O que exatamente deveria ser chamado de "matriz de projeção" no contexto do PCA? - uma matriz $d\times k$ $U$ de autovetores ortonormais não é estritamente uma projeção.

ameba
fonte

3

No seu último parágrafo, você diz que, se as colunas são ortonormais, a projeção ainda não é uma projeção no sentido de uma projeção na álgebra linear. No entanto, isso ocorre apenas porque a matriz não é uma matriz quadrada. Isso se deve mais à notação do que ao princípio. Se você estender a matriz com zeros, então a matriz é uma projeção linear.

Sextus Empiricus

11

@MartijnWeterings Não, acho que não. Pegue o espaço 2D e U, que é 1x2 e fica assim: [sqrt (2) / 2, sqrt (2) / 2] (correspondente à projeção na diagonal). Agora estenda-o com zeros. Não será igual a si próprio ao quadrado.

Ameba

11

Deve ser estendido alguma outra forma, pode ser feito

b Kjetil Halvorsen

2

R (R^{T} R)^{- 1} R^{T}

$R (R^TR)^{-1}R^T$

I

$I$

U

$U$

P^{2} = P

$P^2=P$

Sextus Empiricus

2

R

$R$

1

$d\times k$ $R$ $R$ $x\in \mathbb R^d$ $R$

$p = xR(R^TR)^{-1}R^T$ $p\in\mathbb R^d$

$R$ $R^TR = I\in \mathbb R^{k\times k}$ $x$ $R$

$p = xRR^T$ $p\in\mathbb R^d$

$RR^T\in\mathbb R^{d\times d}$ $(RR^T)^2=RR^TRR^T=RR^T$

$R$ $\mathbb R^k$ $\mathbb R^d$ $x\in\mathbb R^d$ $xRR^T$ $R$ $RR^T$

Ficaria muito grato se você pudesse confirmar / corrigir meu raciocínio aqui.

Referência:

[1] http://www.dankalman.net/AUhome/classes/classesS17/linalg/projections.pdf

Daniel López
fonte

11

R (R^{T} R)^{- 1} R^{T}

$R(R^T R)^{-1} R^T$

11

R R^{T}

$RR^T$

R

$R$

2

R (R^{T} R)^{- 1} R^{T}

$R(R^TR)^{-1}R^T$

(R^{T} R)^{- 1} R^{T}

$(R^TR)^{-1}R^T$

R^{T}

$R^T$

R^{T}

$R^T$

β = (R^{T} R)^{- 1} R^{T} y

$\beta=(R^TR)^{-1}R^Ty$

β

$\beta$

\hat{y} = R (R^{T} R)^{- 1} R^{T} y

$\hat{y}=R(R^TR)^{-1}R^Ty$

β

$\beta$

-1

Se você usar inversão ou permutação de sinal aleatório recomputável antes da transformação Fast Walsh Hadamard, a projeção aleatória é ortogonal.

Sean O'Connor
fonte

A “projeção aleatória”, estritamente falando, não é uma projeção?

Respostas: