Konstruieren von Vektoren in allgemeiner Position

Es sei eine echte ( ) -Matrix mit der Eigenschaft, dass jede Sammlung von Spalten den vollen Rang hat. $k\times n$ $k\le n$ ${\bf A}$ $k$

F: Gibt es eine effiziente Möglichkeit, einen Vektor deterministisch zu finden, sodass die erweiterte Matrix dieselbe Eigenschaft wie : Alle Spalten haben den vollen Rang. ${\bf a}$ ${\bf A}' = [{\bf A}\;{\bf a}]$ ${\bf A}$ $k$

Relevante Nebenbemerkung: Eine Matrix mit dieser Eigenschaft ist der Generator eines Reed-Solomon-Codes: Durch Hinzufügen von Spalten, die die Vandermonde-Struktur beibehalten, bleibt die Rank-Eigenschaft erhalten. $(n,k)$

ds.algorithms linear-algebra matrices coding-theory Dimitris
quelle

Ich bin mir nicht sicher, ob ich Ihren Standpunkt verstehe. Ich benötige , ist kein Problem.

k \leq n

$k\le n$

k = n

$k=n$

Dimitris

@ Jɛ ﬀ E k ändert sich nicht: Im Fall von k = n müssen nur n der (jetzt) n + 1 Spalten den vollen Rang haben. In diesem Fall sollte das Problem einfach sein: Finden Sie eine affine Transformation der Matrix auf eine orthogonale Basis von R ^ n und lassen Sie a den Vektor sein, dessen Bild darunter der All-1s-Vektor ist.

Suresh Venkat

Es scheint mir, dass dies ein Weg sein sollte, dies über den Grassmanian zu tun, aber ich sehe nicht ganz wie.

Suresh Venkat

@Suresh Ja, für den Fall n = k + 1 scheint es in der von Ihnen erwähnten Weise lösbar zu sein. Oder Sie können einfach auswählen , um im Nullraum aller , -Kollektionen von Vektoren zu sein.

a

${\bf a}$

k

$k$

(k - 1)

$(k-1)$

Dimitris

gute Frage. klingt nach einer schwächeren Version des Problems der Überprüfung der eingeschränkten Isometrieeigenschaft, die meines Wissens weit offen ist.

Sasho Nikolov

Antworten:

Wenn Sie gleichmäßig zufällig aus dem Hypercube auswählen , hat die Matrix mit der Wahrscheinlichkeit die gewünschte Eigenschaft . $\mathbf{a}$ $[0,1]^n$ $[\mathbf{A}~ \mathbf{a}]$ $1$

Jeffε
quelle

Ich kann nur zustimmen :). Das Problem tritt auf, wenn Sie überprüfen möchten, ob ein solcher Vektor funktioniert (unabhängig davon, ob dies der Fall ist). Sie müssen Teilmengen von Spalten überprüfen . Dieses Problem der Überprüfung wird relevanter, wenn Sie endliche Felder (fester Reihenfolge) betrachten, aber ich habe versucht, nicht darüber zu sprechen.

(\binom{n}{k})

${{n}\choose{k}}$

Dimitris

Die Frage fragt speziell nach einem effizienten deterministischen Algorithmus. Wenn Sie etwas Ähnliches beantworten, aber die in der Frage angegebene Bedingung nicht erfüllen, sollten Sie dies meiner Meinung nach ausdrücklich sagen.

Tsuyoshi Ito

@ TsuyoshiWas magst du nicht Kätzchen? :)

Suresh Venkat

@Suresh: In der Praxis wäre es amüsant, wenn mein Computer plötzlich zu einem Kätzchen wird. Theoretisch muss man jedoch zuerst ein Kätzchen definieren.

Tsuyoshi Ito

@ Jɛ ﬀ E Vielleicht hätte ich klarstellen sollen, warum diese Frage von Interesse ist. Die eigentliche Frage ist dieselbe, aber über endliche Felder, aber ich neige dazu zu denken, dass Felder lineare Algebra-Fragen komplizieren. Die Anwendung ist das Design von "guten" Codegeneratormatrizen. Mit Tools wie dem Schwartz-Zippel-Lemma können zufällige Einträge (iid-Einträge) angezeigt werden, um die Eigenschaft whp zu erfüllen. Für dieses Problem benötigt SZ normalerweise Feldreihenfolgen von und Sie können nicht effizient überprüfen, ob die Matrizen wirklich funktionieren. Warum ist das wichtig? Weil Codes, die höchstwahrscheinlich zuverlässig sind, manchmal nicht bevorzugt werden.

O (2^{k})

$O(2^k)$

Dimitris