Problem mit nicht orthogonalen Vektoren

8

Betrachten Sie die folgenden Probleme:

Problem der orthogonalen Vektoren

Eingabe: Eine Menge SS von Booleschen Vektoren mit der Länge .n dnd

Frage: unterschiedliche Vektoren und so dass ?v 1 v 2S v 1v 2 = 0v1v2Sv1v2=0

Problem mit nicht orthogonalen Vektoren

Eingabe: Eine Menge von Booleschen Vektoren mit jeweils der Länge und einer positiven ganzen Zahl .S n d kSndk

Frage: unterschiedliche Vektoren und so dass ?v 1 v 2S v 1v 2kv1v2Sv1v2k

Welche Beziehung besteht zwischen diesen beiden Problemen?

Hier sind insbesondere einige spezifischere Fragen, über die ich mich gewundert habe:

(1) Scheint eines dieser Probleme schwieriger zu sein als das andere?

(2) Ich bin nicht sicher, wie der aktuelle Algorithmus für OVP aussieht, aber können Sie für eines dieser Probleme eine Obergrenze erhalten, die besser ist als die O ( n 2d ) -ZeitO(n2d) ?

(3) Macht die Behebung von kk einen Unterschied für die Komplexität des zweiten Problems?

Mit v 1v 2v1v2 meine ich das innere Produkt von v 1v1 und v 2v2 über R dRd .

Bearbeiten: Die meisten Antworten bieten wirklich gute Einblicke, wenn dd klein ist.

Was kann gesagt werden, wenn dd größer ist? Sagen Sie d = nd=n oder d = nd=n oder mindestensd=nαd=nαfür einige.α > 0α>0

Michael Wehar
quelle
4
Zu (2): Soweit ich weiß, wurde in diesem Artikel der bekannteste Algorithmus zur Lösung von OVP festgelegt . Es hat die Komplexität O ( n 2 - 1O ( log ( dlog n ))).
On21O(log(dlogn)).
Die Verbesserung dieses Ergebnisses aufO(n2-ε)O(n2ε)für eine Konstanteεεist ein bekanntes offenes Problem und wird als unwahrscheinlich angesehen, da dies dieVermutung einer starken exponentiellen Zeithypothese verfälschenwürde.
Geoffroy Couteau
Das zweite Problem ist auch in O ( n k ( dk ) )Zeit. Wählen Sie einfachkPositionen und prüfen Sie, ob zwei Vektoren alle Einsen an diesen Positionen haben. O(nk(dk))k
Michael Wehar
1
Ein Hinweis zur obigen Zeitgrenze für OVP: Die Zeitgrenze erfordert auch d <= 2 ^ (sqrt (log n)), andernfalls dauert die Zwischenkonstruktion eines probabilistischen Polynoms zu lange.
Ryan Williams
2
Über großes d: Algorithmen für die rechteckige Matrixmultiplikation schlagen n ^ 2 d bei der Berechnung aller Punktprodukte. Wenn d <n ^ 0,3 ist, wird die Zeitgrenze zu n ^ (2 + o (1)).
Rasmus Pagh
1
@ MichaelWehar: Genau. Ich denke, das beste Ergebnis ist François Le Gall zu verdanken
Rasmus Pagh

Antworten:

8

Wenn k als Teil der Eingabe angegeben wird, entspricht das zweite Problem dem monochromatischen Max-IP-Problem (bei S { 0 , 1 } d finden Sie max ( a , b ) S , a b a b ). .kS.{ 0 , 1 }dmax( a , b ) S.,abab

Kürzlich haben ich und Ryan Williams eine (noch nicht veröffentlichte) Arbeit, die zeigt, dass wenn d = O ( log n ) , OVP und eine bichromatische Version von Max-IP (gegeben A , B , max ( a , b ) A × B a finden b ) ist tatsächlich äquivalent: Das heißt, wenn einer von ihnen einen n 2 - ε- Zeitalgorithmus hat, tut dies auch der andere. (Die Reduzierung von OVP auf Max-IP ist bekannt, die neue Reduzierung hier ist die von Max-IP auf OVP).d=O(logn)EIN,Bmax( a ,b)A×Beinbn2 - ε

Da die monochromatische Version von Max-IP auf die bichromatische Version reduziert werden kann, impliziert das obige Ergebnis auch, dass bei d = O ( log n ) monochromatisches Max-IP auf OVP reduziert werden kann.d=O(logn )

Ich glaube, es ist eine offene Frage, ob OVP auf monochromatisches Max-IP reduziert werden kann. Dies hängt auch eng mit der Ermittlung der OV-Härte für das engste Paarproblem zusammen (siehe z. B. Zur Komplexität des engsten Paares über das Polarpaar der Punktmengen ).

Für monochromatische Max-IP gibt es einen Algorithmus mit Laufzeit n 2 - 1 / ~ O ( ( d / log n ) 1 / 3 ) Algorithmus von Alman, Chan und Williams (auch von Rasmus wies darauf hin), für die ich glauben ist der Stand der Technik. Während der beste Algorithmus für OVP in n 2 - 1 / O ( log c ) läuft, wenn d = c log n ist , was erheblich schneller ist.n21/O˜((d/logn)1/3)n21/O(logc)d=clogn

Die ungefähre Version von Max-IP wird auch in diesem Artikel über die Härte des ungefähren und exakten (bichromatischen) maximalen inneren Produkts untersucht , der eine Charakterisierung für den bichromatischen Fall liefert (dh für welche Dimensionen d und ungefähres Verhältnis t , das Problem kann in n 2 - ε Zeit gelöst werden?). Der Algorithmus in diesem Artikel funktioniert auch für den monochromatischen Fall.dtn2ε

Lijie Chen
quelle
Hat die n 2 - 1 / ~ O ( ( d / log n ) 1 / 3 ) Algorithmus einige Grenzen auf erfordern d ? n21/O˜((d/logn)1/3)d
Michael Wehar
6

Wenn k = O ( log n ), glaube ich, dass die Techniken von Alman, Chan und Williams die bekannteste Lösung für das Problem der nicht orthogonalen Vektoren liefern. (Sie formulieren es anders als ein Hamming-Problem mit den nächsten Paaren, aber dies entspricht bis zu Poly ( d ) -Faktoren.)k=O(logn)d

Ohne Bindung an k ist eine bichromatische Version des Problems der nicht orthogonalen Vektoren bis zu einem Faktor d log n mindestens so schwer wie das Problem der orthogonalen Vektoren (OVP) . Beachten Sie zunächst, dass wir mit einem Faktor log n Overhead auf die bichromatische Version von OVP reduzieren können, wobei S = S 1S 2 (disjunkte Vereinigung in Mengen unterschiedlicher "Farbe") und wir nur an bichromatischen orthogonalen Paaren interessiert sind ( v 1) , v 2 ) S 1 × S 2 . Zweitens mit einem Faktor dkdlognlognS=S1S2(v1,v2)S1×S2dOverhead können wir auf den Sonderfall der bichromatischen OVP reduzieren, bei dem alle Vektoren in S 1 das gleiche Hamming-Gewicht w haben . Schließlich wird durch Invertieren aller Vektoren in S 2 erhalten S ' 2 sehen wir , dass S 1 und S 2 haben ein orthogonales Paar , wenn und nur wenn S 1 und S ' 2 ein Paar von Vektoren mit Skalarprodukt zumindest w . Ich bin mir nicht sicher, ob es eine effiziente Reduktion vom Problem der bichromatischen nichtorthogonalen Vektoren auf die von Ihnen beschriebene monochromatische Version gibt.S1wS2S2S1S2S1S2w

Wenn Sie eine Annäherung zulassen, gibt es eine Reihe neuerer Ergebnisse für das Problem der bichromatischen nicht orthogonalen Vektoren (häufig als Problem der Suche nach dem maximalen inneren Produkt bezeichnet). Siehe zB dieses Papier und seine Referenzen.

Rasmus Pagh
quelle
0

Äquivalenzen:

Das Problem der nicht orthogonalen Vektoren (wie oben definiert) für eine Menge SS von nn Booleschen Vektoren mit jeweils der Länge dd und einer positiven ganzen Zahl kk ist wie folgt äquivalent:

  • Die Suche nach einem 22 durch kk Submatrix von 1 ist in einem gegebenen nn von dd Boolesche Matrix.

  • Finden eines vollständigen K 2 , k-K2,k Untergraphen in einem gegebenen zweigeteilten Graphen, wobei der erste Scheitelpunktsatz die Größe nn und der zweite Scheitelpunktsatz die Größe d hatd .

Naiver Algorithmus:

Der naive Ansatz für das Problem der nicht orthogonalen Vektoren läuft in O ( d n 2 ),O(dn2) da O ( d n 2 )O(dn2) Zeit benötigt, um das Punktprodukt jedes Vektorpaars naiv zu berechnen.

Antwort auf die Fragen (2) & (3):

Ja, es gibt mehrere Algorithmen, die in verschiedenen Fällen effizienter sind.

Erste Ansatz:

Wir können das Problem der nicht orthogonalen Vektoren in O ( d n + k n 2 )O(dn+kn2) lösen .

Anmerkung: Da das Punktprodukt zweier boolescher Vektoren der Länge dd durch dd begrenzt werden muss , ist das Problem nur dann sinnvoll, wenn k d istkd .

Beweis. Lass einen Satz SS von nn Booleschen Vektoren mit jeweils der Länge dd und einer positiven ganzen Zahl kk gegeben. Betrachtenein Aufzählungs { s i } i [ n ]{si}i[n] der Elemente von SS .

Erstellen eine hashmap mm von Paaren ( a , b ) [ n ] × [ n ](a,b)[n]×[n] zu NN . Zu Beginn ordnet mm jede Eingabe dem Wert 0 zu.

Für jedes i [ d ] macheni[d] wir Folgendes. Zählen Sie durch Paare von Vektoren s asa , s b auf,sb so dass a < ba<b , das i-i te Bit von s asa 1 und das i-i te Bit von s b 1sb ist. Für jedes solche s asa und s b,sb wenn m ( a , b ) = k - 1m(a,b)=k1 , dann s asa und s bsbsind nicht orthogonal, dh s as bksasbk . Andernfalls erhöhen Sie m ( a , b )m(a,b) und fahren fort.

Wenn wir die Aufzählung beenden, ist kein Vektorpaar nicht orthogonal.

Es dauert O ( n d )O(nd) Zeit, um jedes Bit jedes Vektors zu durchsuchen. Dann dauert es zusätzliche Zeit, um Vektorpaare aufzulisten. Weil es höchstens gibt ( n2 )(n2) Paare von Vektoren und jedes Paar können höchstensk-1k1Mal auftreten, bevor gezeigt wurde, dass sie nicht orthogonal sind. Die Aufzählung von Paaren dauert höchstensO(kn2)O(kn2). Daher ist die GesamtlaufzeitO(dn+kn2)O(dn+kn2).

Anmerkung: Wenn k = 2 istk=2 , können wir diesen Ansatz für die O ( n d ) -ZeitO(nd) verbessern . Dies liegt daran , dass wir bei k = 2k=2 das Finden eines Paares nicht orthogonaler Vektoren unter nn Booleschen Vektoren der Länge dd auf das Finden eines Paares nicht orthogonaler Vektoren unter dd Booleschen Vektoren der Länge nn reduzieren können .

Zweiter Ansatz:

Wir können das Problem der nicht orthogonalen Vektoren in O ( k ( dk )n)O(k(dk)n)Zeit.

Beweis. Es sei eine Menge SS von nn Booleschen Vektoren mit jeweils der Länge dd und einer positiven ganzen Zahl kk gegeben.

Zählen Sie durch die Mengen P [ d ] auf,P[d] so dass PP die Größe k hatk . Überprüfen Sie für jeden Vektor v SvS , ob vv alle Einsen an den Positionen in P hatP . Wenn es zwei Vektoren gibt, die alle Einsen an den Positionen in P habenP , haben wir zwei nicht orthogonale Vektoren gefunden.

Insgesamt gibt es ( dk )(dk) Wahlmöglichkeiten fürPP. Und für jede Auswahl scannen wirknknBits von den Vektoren. Insgesamt ist die Laufzeit alsoO(k ( dk )n)O(k(dk)n).

Dritter Ansatz:

Wenn d n istdn , können wir das Problem der nicht orthongalen Vektoren in der Zeit O ( d ω - 2n 2 )O(dω2n2) lösen, wobei ωω der Exponent für die Multiplikation der ganzzahligen Matrix ist. Wenn d > n istd>n , können wir das Problem der nicht orthongalen Vektoren in der Zeit O ( d n ω - 1 )O(dnω1) lösen .

Hinweis: Wie von @Rasmus Pagh hervorgehoben, können wir diesen Algorithmus auf die Zeit O ( n 2 + o ( 1 ) )O(n2+o(1)) verbessern, wenn d n 0,3 istdn0.3 . Weitere Informationen finden Sie hier: https://arxiv.org/abs/1204.1111

Beweis. Es sei eine Menge SS von nn Booleschen Vektoren mit jeweils der Länge dd und einer positiven ganzen Zahl kk gegeben.

Betrachten wir Matrizen AA und BB . Die erste Matrix AA hat die Dimensionen nn mal d,d wobei jede Zeile von AA ein Vektor von S istS . Die zweite Matrix BB hat die Dimensionen dd mal n,n wobei jede Spalte von BB ein Vektor von S istS .

Wir können das Punktprodukt jedes Vektorpaars in SS berechnen, indem wir A B unterAB Verwendung von Algorithmen zur schnellen Multiplikation der ganzzahligen Matrix berechnen.

Wenn d n istdn , besteht ein Ansatz darin, die rechteckige Matrixmultiplikation in ( n) umzuwandelnd )2(nd)2Multiplikationen des QuadratsddmitddMatrizen. Durch Verwendung der schnellen Quadratmatrixmultiplikation können wir alle Multiplikationen inO((n)berechnend )2dω)=O(dω-2n2)O((nd)2dω)=O(dω2n2)Zeit.

Wenn d > n istd>n , besteht ein Ansatz darin, die rechteckige Matrixmultiplikation in d umzuwandelnndn Multiplikationen des QuadratsnnmitnnMatrizen. Durch Verwendung der schnellen Quadratmatrixmultiplikation können wir alle Multiplikationen inO((dn )nω)=O(dnω-1)O((dn)nω)=O(dnω1)Zeit.

Michael Wehar
quelle
Vergleichen wir diese drei Ansätze in verschiedenen Fällen. Fall 1: Wenn k fest ist und d = O ( log 2 ( n ) ) ist , ist der zweite Ansatz am effizientesten. kd=O(log2(n))
Michael Wehar
Fall 2: Wenn k = O ( log 2 ( n ) ) und d = O ( n α ) für jedes α ( 0,3 , 1 ) ist , ist der erste Ansatz manchmal am effizientesten. k=O(log2(n))d=O(nα)α(0.3,1)
Michael Wehar
Fall 3: Wenn d n 0,3 ist , ist der dritte Fall manchmal am effizientesten. dn0.3
Michael Wehar
Fall 4: Wenn d und k größer als n sind , ist der dritte Ansatz manchmal am effizientesten.
Michael Wehar
Hinweis: Der erste Ansatz ist dem Algorithmus zum Finden eines Vierzyklus in einem Diagramm in quadratischer Zeit ziemlich ähnlich. Siehe hier: sciencedirect.com/science/article/pii/S0304020808730196
Michael Wehar