Vi anser att problemet med att anpassa ett par databaser med gemensamt Gaussiska funktioner. Vi anser att två algoritmer, fullständig databasanpassning via MAP uppskattning bland alla möjliga databasanpassningar, och partiell anpassning via en tröskelmetod för logsannolikhet förhållande. Vi härleder villkor om ömsesidig information mellan funktionspar, identifiera de system där algoritmerna garanteras att utföra tillförlitligt och de där de inte kan förväntas lyckas. Variabler, införande av en ny korrelationsmått som kännetecknar genomförbarheten av anpassning [2]. Takbiri m.fl. har undersökt ett relaterat problem där funktionen hos varje användare är Gaussian med karakteristisk statistik och har korrelation med andra användarfunktioner [3]. I denna miljö försöker en motståndare med perfekt kunskap om systemstatistik matcha funktioner med den karakteristiska användarstatistiken. Detta följer författarnas tidigare studier av samma inställning för diskreta värden och med data obfuscation [4], [5]. Problemet med att anpassa databasen är kopplat till det allmänt studerade grafuppriktningsproblemet. I den inställningen är varje funktion associerad med ett par anonymiserade användare. I det enklaste fallet är funktionen en Bernoulli slumpmässig variabel som anger närvaron eller frånvaron av en kant mellan användarna. En senaste raden av arbete har karakteriserat informationen teoretiska gränser för grafen anpassning problem [6, 7, 8]. Problemet med att anpassa korrelerade Wignermatriser, där varje funktion är en Gaussisk slumpmässig variabel, har fungerat som en proxy för att förstå effektiviteten av graf anpassning algoritmer [9]. Notering Vi betecknar slumpmässiga variabler med versaler och fasta värden med små bokstäver. För en uppsättning S och ändliga uppsättningar T, U, Vi betecknar med S T ×U uppsättningen matriser med poster i S, rader indexerade av T och kolumner indexerade av U. Vi markerar vektorer med pilar och skriver matriser i fetstil. Eftersom vissa matris z, vi betecknar dess i-th rad av z i *, j-th kolumn av z * j och dess (i, j)-th inträde av z ij. Vi betecknar identitetsmatrisen med rader och kolumner indexerade av T av I T. När indexeringen uppsättningen är tydlig från sammanhang, kommer vi att släppa superscriptet. Vi betecknar uppsättningen heltal från 1 till n av [n]. I den här modellen är en databas bara en funktion från en uppsättning användare till ett visst utrymme. Värdet av funktionen för en användare u är databasposten för den användaren. Cullina, Mittal och Kiyavash anses databasposter i finita alfabet [2]. I detta papper, vi anser databasposter som är ändliga dimensionella verkliga vektorer provtagna från en gaussian distribution. Vi ges två uppsättningar av användaridentifierare, U och V, med  på U =  och V = n. Vi uttrycker innehållet i databaser av matriser A  med R U ×[da] och B med R V×[d b ], så d a och d b är längden på funktionsvektorer. Det finns en naturlig bijektiv överensstämmelse mellan identifieringsuppsättningarna, dvs. varje identifierare i en uppsättning är relaterad till exakt en identifierare i den andra uppsättningen. Vi uttrycker denna korrespondens av bijective matchande M  på U × V. Låt p X Y vara densiteten av gemensamt gaussian slumpvariabler Den densitet p AB med M definieras enligt följande. För varje (u, v) M, (A u *, B v * ) P X Y och dessa n slumpmässiga variabler är oberoende: Den matchande M är jämnt fördelade över n! bijective matchningar mellan U och V. Databasanpassning problem är att återställa M från AB, med tanke på kunskap om p X Y. Observera att raderna i A är i.i.d. och att A är oberoende av M. Detsamma gäller för B. Med andra ord, genom att undersöka en databas, en observatör lär sig ingenting om M. Ett par databaser illustreras i Figur 1.
Databasanpassning är en viktig variant av grafanpassning, studerad i REF.
Database Alignment with Gaussian Features
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}