We consider the problem of aligning a pair of databases with jointly Gaussian features. We consider two algorithms, complete database alignment via MAP estimation among all possible database alignments, and partial alignment via a thresholding approach of log likelihood ratios. We derive conditions on mutual information between feature pairs, identifying the regimes where the algorithms are guaranteed to perform reliably and those where they cannot be expected to succeed. variables, introducing a new correlation measure characterizing the feasibility of alignment [2] . Takbiri et al. have investigated a related problem where the feature of each user is Gaussian with characteristic statistics and has correlation with other user features [3] . In this setting an adversary with perfect knowledge of system statistics attempts to match features with the characteristic user statistics. This follows the authors' previous studies of the same setting for discrete valued features and with data obfuscation [4], [5] . The database alignment problem is connected to the widely studied graph alignment problem. In that setting, each feature is associated with a pair of anonymized users. In the simplest case, the feature is a Bernoulli random variable indicating the presence or absence of an edge between the users. A recent line of work has characterized the information theoretic limits of the graph alignment problem [6, 7, 8] . The problem of aligning correlated Wigner matrices, in which each feature is a Gaussian random variable, has served as a proxy for understanding the effectiveness of graph alignment algorithms [9]. Notation We denote random variables by capital letters and fixed values by lowercase letters. For a set S and finite sets T , U , we denote by S T ×U the set of matrices with entries in S, rows indexed by T and columns indexed by U . We mark vectors with arrows and write matrices in boldface. Given some matrix z, we denote its i-th row by z i * , j-th column by z * j and its (i, j)-th entry by z ij . We denote the identity matrix with rows and columns indexed by T by I T . When the indexing set is clear from context, we will drop the superscript. We denote the set of integers from 1 to n by [n]. In this model, a database is just a function from a set of users to some space. The value of the function for a user u is the database entry for that user. Cullina, Mittal, and Kiyavash considered database entries in finite alphabets [2] . In this paper, we consider database entries that are finite dimensional real vectors sampled from a gaussian distribution. We are given two sets of user identifiers, U and V, with |U | = |V| = n. We express the content of databases by matrices A ∈ R U ×[da] and B ∈ R V×[d b ] , so d a and d b are the lengths of feature vectors. There exists a natural bijective correspondence between the identifier sets, i.e. each identifier in one set is related to exactly one identifier in the other set. We express this correspondence by the bijective matching M ⊆ U × V. Let p X Y be the density of jointly gaussian random variables The density p AB|M is defined as follows. For each (u, v) ∈ M , (A u * , B v * ) ∼ p X Y and these n random variables are independent: The matching M is uniformly distributed over the n! bijective matchings between U and V. The database alignment problem is to recover M from AB, given knowledge of p X Y . Observe that the rows of A are i.i.d. and that A is independent of M . The same is true for B. In other words, by examining one database, an observer learns nothing about M . A pair of databases are illustrated in Figure 1 .
Database alignment is an important variant of graph alignment, studied in REF .
Database Alignment with Gaussian Features
ArXiv
ArXiv
Mathematics Computer Science