Ist „zufällige Projektion“ streng genommen keine Projektion?

10

Aktuelle Implementierungen des Zufallsprojektionsalgorithmus reduzieren die Dimensionalität von Datenproben, indem sie von Rd auf Rk Verwendung einer d×k Projektionsmatrix R abgebildet werden, deren Einträge aus einer geeigneten Verteilung stammen (zum Beispiel aus N(0,1) ):

x=1kxR

Praktischerweise gibt es theoretische Beweise dafür, dass diese Abbildung ungefähr paarweise Abstände beibehält.

Kürzlich habe ich jedoch diese Notizen gefunden , in denen der Autor behauptet, dass diese Abbildung mit einer Zufallsmatrix keine Projektion im strengen linearen algebraischen Sinne des Wortes ist (Seite 6). Aus den dort gegebenen Erklärungen geht hervor, dass die Spalten von R nicht streng orthogonal sind, wenn ihre Einträge unabhängig von N(0,1) . Daher können frühere Versionen von RP, bei denen die Orthogonalität der Spalten von R erzwungen wurde, als Projektion betrachtet werden.

Können Sie eine detailliertere Erklärung geben für (1) was ist die Definition einer Projektion in diesem strengen Sinne und (2) warum ist RP keine Projektion unter dieser Definition?.

Daniel López
quelle
1
Antworten auf (1) finden Sie auf unserer Website . Die Behauptung (2) ist sofort da , wenn die Spalten waren immer orthogonal, ihre Einträge nicht unabhängig sein könnten.
whuber

Antworten:

4
  1. Was ist die Definition einer Projektion in diesem strengen (linearen algebraischen) Sinne (des Wortes)?

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

    In der linearen Algebra und Funktionsanalyse, ist eine Projektion eine lineare Transformation P von einem Vektorraum , um sich selbst , daß eine solche P2=P . Das heißt, wenn P zweimal auf einen Wert angewendet wird, ergibt sich das gleiche Ergebnis, als ob es einmal angewendet worden wäre (idempotent).

    Für die orthogonale Projektion oder Vektorprojektion haben Sie das

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

    Eine orthogonale Projektion ist eine Projektion, für die der Bereich U und der Nullraum V orthogonale Teilräume sind.

  2. Warum ist RP keine Projektion unter dieser Definition?

    Michael Mahoney schreibt in Ihren Vorlesungsunterlagen, dass es davon abhängt, wie die RP aufgebaut ist , ob die RP eine Projektion im traditionellen linearen algebraischen Sinne ist oder nicht. Dies tut er im dritten und vierten Punkt:

    Drittens, wenn die Zufallsvektoren genau orthogonal wären (wie sie tatsächlich in den ursprünglichen JL-Konstruktionen waren), dann hätten wir, dass die JL-Projektion eine orthogonale Projektion wäre

    ...

    Obwohl dies für Gaußsche, {±} Zufallsvariablen und die meisten anderen Konstruktionen falsch ist , kann man beweisen, dass die resultierenden Vektoren ungefähr Einheitslänge und ungefähr orthogonal sind

    ...

    das ist "gut genug".

    Sie können also im Prinzip die zufällige Projektion mit einer anderen Konstruktion durchführen, die auf orthogonale Matrizen beschränkt ist (obwohl dies nicht erforderlich ist). Siehe zum Beispiel das Originalwerk:

    Johnson, William B. und Joram Lindenstrauss. "Erweiterungen von Lipschitz-Mappings in einen Hilbert-Raum." Zeitgenössische Mathematik 26.189-206 (1984): 1.

    ... wenn man zufällig eine orthogonale Projektion mit Rang k auf l n 2 wähltl2n

    ...

    Qkl2nσO(n)l2n

    f:(O(n),σ)L(l2n)
    f(u)=UQU
    k

    Der Wikipedia-Eintrag beschreibt die zufällige Projektion auf diese Weise (dasselbe wird in den Vorlesungsunterlagen auf den Seiten 10 und 11 erwähnt).

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

    Sd1

    Diese Orthogonalität erhalten Sie jedoch im Allgemeinen nicht, wenn Sie alle Matrixeinträge in der Matrix als zufällige und unabhängige Variablen mit einer Normalverteilung verwenden (wie Whuber in seinem Kommentar mit einer sehr einfachen Konsequenz erwähnte: "Wenn die Spalten immer orthogonal wären, könnten ihre Einträge nicht unabhängig sein ").

    RP=RTRb=RTxx=Rb=RTRxRTR

    P=RTRU

    range(PTP){0,1}

    PRP=RTRR

    Eine zufällige Projektion durch verschiedene Konstruktionen, beispielsweise die Verwendung zufälliger Einträge in der Matrix, entspricht also nicht genau einer orthogonalen Projektion. Aber es ist rechnerisch einfacher und laut Michael Mahoney „gut genug“.

Sextus Empiricus
quelle
1
P=RRTRRd×kN(0,1)P2=PP{0,1}RRRTR
1
@ DanielLópez Ich habe es aktualisiert.
Sextus Empiricus
6

Das ist richtig: "Zufallsprojektion" ist streng genommen keine Projektion.

PP2=P

d×kRkd

Rd×kU

Amöbe sagt Reinstate Monica
quelle
3
In Ihrem letzten Absatz sagen Sie, dass die Projektion bei orthonormalen Spalten immer noch keine Projektion im Sinne einer Projektion in der linearen Algebra ist. Dies liegt jedoch nur daran, dass die Matrix keine quadratische Matrix ist. Dies ist mehr auf die Notation als auf das Prinzip zurückzuführen. Wenn Sie die Matrix mit Nullen erweitern, ist die Matrix eine lineare Projektion.
Sextus Empiricus
1
@MartijnWeterings Nein, das glaube ich nicht. Nehmen Sie den 2D-Raum und U, das 1x2 ist und so aussieht: [sqrt (2) / 2, sqrt (2) / 2] (entsprechend der Projektion auf der Diagonale). Erweitern Sie es jetzt mit Nullen. Es wird nicht gleich quadratisch sein.
Amöbe sagt Reinstate Monica
1
Es sollte auf eine andere Weise erweitert werden, kann getan werden
kjetil b halvorsen
2
R(RTR)1RTIUP2=P
Sextus Empiricus
2
R
1

d×kRRxRdR

p=xR(RTR)1RTpRd

RRTR=IRk×kxR

p=xRRTpRd

RRTRd×d(RRT)2=RRTRRT=RRT

RRkRdxRdxRRTRRRT

Ich wäre Ihnen dankbar, wenn Sie meine Argumentation hier bestätigen / korrigieren könnten.

Referenz:

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

Daniel López
quelle
1
R(RTR)1RT
1
RRTR
2
R(RTR)1RT(RTR)1RTRTRTβ=(RTR)1RTyβy^=R(RTR)1RTyβ
-1

Wenn Sie vor der Fast Walsh Hadamard-Transformation ein umrechnungsfähiges Umkehren oder Permutieren von Zufallszeichen verwenden, ist die zufällige Projektion orthogonal.

Sean O'Connor
quelle