Orthogonale Matrix mit Zeilenvekotren gleicher Norm



  • Hallo

    Ich möchte gerne versuchen das folgende Programm zu schreiben:

    Ich will eine Matrix erstellen lassen, mit L Zeilen und N Spalten. Die Zeilenvektoren sollen orthogonal zueinander sein, also kanonisches Skalarprodukt Null. Die Norm eines jeden Zeilenvektors soll gleich sein. Das bedeutet, dass in einer Zeile nun mehre 1 er stehen dürfen, in jeder Zeile aber gleich viel. Ferner darf wegen der Orthogonalität in keiner Spalte mehr als eine 1 stehen. Die Anzahl der 1 er die in den Zeilen stehen möchte ich dabei als Parameter steuern können. Natürlich muss dieser so gewählt sein, dass die Matrix noch so existiert.

    Die C++ Implementierung davon möchte ich selbst versuchen. Woran ich allerdings gerade scheitere ist das konzeptionelle, numerische Vorgehen wie ich so eine Matrix konstruieren könnte.

    Danke für Tipps und Grüße



  • Ich verstehe zwar nicht ganz, warum deine Matrix nur aus 1er und 0en bestehen muss, da es sonst noch viel mehr Möglichkeiten gäbe, Matrizen mit orthonormalen Zeilenvektoren zu konstruieren, aber okay.

    Der erste Schritt wäre wohl mal zu prüfen, ob die Spaltenzahl durch die angegebene Anzahl der 1er pro Zeile mal Zeilenzahl teilbar ist, ansonsten wird die Normierungsbedingung verletzt.

    Und dann? Willst du nun einfach nur irgendeine oder alle möglichen Matrizen konstruieren? Letzteres könnten je nach Dimension ganz schön viele werden.

    Edit: Das wären dann
    i=0M1(Nni)!(Nn(i+1))!\prod\limits_{i=0}^{M-1}\dfrac{(N-ni)!}{\left(N-n(i+1)\right)!}
    Möglichkeiten (bei MxN-Matrix mit n 1er pro Zeile und ohne Gewähr).



  • Danke für den Hinweis.

    Ich habe es eben hinbekommen 🙂 Hier mein Code falls jemand wissen möchte wie ich das gemacht habe:

    //Programm erstellt binäre (L x N) Matrix, Zeilenvektoren zueinander orthogonal, Jeder Vektor hat gleiche Norm
    //N muss durch I*L teilbar sein (I=Zahl der 1er pro Zeile
    #include <iostream> 
    #include <stdlib.h>
    #include <vector>
    #include <iterator>
    #include <stdlib.h>
    #include <algorithm>
    #include <sstream>
    
    #define ADSIZE 16           //Anzahl der Spalten
    #define MAX_MUSTER 4       //Anzahl der Zeilen
    #define I 4               //Zahl der 1-er in den Zeilenvektoren der Muster
    
    using namespace std;
    //=============================================
    //Fisher-Yates-Shuffle-Algorithmus
    void FisherYates(std::vector<int>& vec)
    {
        int n = vec.size();
        for (int i = n - 1; i > 0; --i)
        {
            std::swap(vec[i], vec[rand() % (i + 1)]);
        }
    }
    //=============================================
    int main () {                                      
    int ik,il;
    
    int Sequenz[ADSIZE];
    for(il=0; il<ADSIZE; il++){Sequenz[il]=il;}
    
    vector<int> sequenz;
    sequenz.insert( sequenz.begin() , Sequenz , Sequenz + ADSIZE ) ; 
    
    FisherYates(sequenz);
    //std::copy(sequenz.begin(), sequenz.end(), std::ostream_iterator<int>(std::cout, " "));
    
    vector< vector<int> > muster( MAX_MUSTER,vector<int>(ADSIZE) );
    
    //Setze zueinander orthogonale Zeilenvektoren mit gleicher Norm
    std::stringstream sstr;
    int z;
    z=ADSIZE/I;
    il=0;
    
    for(ik=0; ik<MAX_MUSTER; ik++)
    {   
    
       for(sstr.str()[il]; il<z; il++)
       {
       muster[ik][sequenz[il]]=1;          
       }  
    z=z+I;
    }
    
    //Ausgabe der zueinander orthonormalen Zeilenvektoren
    for(ik=0; ik<MAX_MUSTER; ik++)
    {
        for(il=0; il<ADSIZE; il++)
        {
        cout << " " << muster[ik][il];
        }
    cout << "\n";
    }
    
    //=============================================
    return 0;                                                                                             
    }
    //=============================================
    

    @Jodocus
    Es dürfen nur Nullen und Einser sein, weil ich unter anderem bei neuronalen (Attraktor-) Netzen untersuchen möchte, wie die Überlappe der Skalarprodukte von Attraktoren und gelernten Bilder miteinander zusammenhängen. Man sollte die Attraktoren zerlegen können in die vom Netz gespeicherten Muster und die Hoffnung/Vermutung ist, dass man Wahrscheinlichkeiten für ein Testmuster ausrechnen könnte in Analogie zum Diracformalismus in der Quantenmechanik (ohne das hier natürlich von QM die Rede ist). Motivation dazu ist, dass unter bestimmten Umständen die Adjazenzmatrix des Netzes auch eine Projektionsmatrix ist. Allerdings hängt es natürlich davon ab wie man die Bilder kodiert. Hat man nur zwei mögliche Zustände (Schwarz und Weiß), so kann man das Bild binär {0,1} oder bipolar {-1,1} speichern. Das ist insofern interessant, weil das gleiche Bild vom Attraktornetz anderes Konvergenzverhalten zeigt (weil die Adjazenzmatrix natürlich eine Andere ist). Biologischer betrachtet könnte man sagen, dass in solch einem Modell ein Neuron binär kodiert entweder feuert mit Gewicht 1, oder eben ruht, wohingegen bei der bipolaren Kodierung ein Neuron mit Gewicht 1 feuert, aber auch inhibitorisch (abschwächend) feuern kann.

    Das durch die Kodierung das Netz anders wird kann man auch ohne Computer ganz gut an der Energie sehen, die man einem solchen Netz zuordnet. Beim finden eines Attraktors wird diese von Iteration zu Iteration niedriger. Da man jedoch die Kodierungen ineinander umrechnen kann, durch s=2x-1, s ∈ {-1,1}, x ∈ {0,1}, erhält man bei der Energie plötzlich Kreuzterme die in der anderen Kodierung nicht vorhanden sind.

    Ich habe entsprechend auch noch vor das selbe Programm in bipolarer Kodierung der Vektoren zu schreiben. Damit man dann die Ergebnisse aus dem Netz mit beiden Kodierungen vergleichen kann. Natürlich muss man sich zusätzlich noch Gedanken machen wie die Aktivierungsfunktion das Verhalten ändert. Der Typische Ansatz mit einer Stufenfunktion ist eigentlich ziemich schlecht für theoretische Überlegungen, weil man dadurch die Linearität verliert. Besser ist es da z.B. den Hyperbolicus Tangens linear zu nähern als Aktivierung. Dann ist die Hebbsche Lernregel nämlich einfache Matrixmultiplikation. Später soll dann ein dritter Zustand dazu kommen {-1, 0, 1} aber eines nach dem anderen. Vorher muss ich noch viel C++ lernen. 🙂

    Daher auch die Notationen in meinem Code. ADSIZE für die Größe der Adjazenzmatrix und eigentlich damit gemeint die Anzahl der Neuronen und MAX_MUSTER für die Zahl der gespeicherten Bilder.


Anmelden zum Antworten