Systems and methods for compressing structured data via latent variable estimation

Abstract

A computer-implemented method for compressing structured data or semi-structured data is provided. The method comprises: (a) estimating one or more latent variables associated with rows or columns of the structured data or semi-structured data; (b) partitioning the structured data or semi-structured data in one or more blocks according to the one or more one or more latent variables; (c) applying a sequential encoding algorithm to each of the blocks; and (d) appending a compressed encoding of the one or more latent variables.

Claims

1. A computer-implemented method for compressing structured data or semi-structured data, comprising: (a) estimating latent variables associated with rows or columns of the structured data or semi-structured data; (b) partitioning the structured data or the semi-structured data into one or more blocks according to the latent variables; (c) applying a sequential encoding algorithm to each of the one or more blocks; and (d) appending a compressed encoding of the latent variables to the compressed encoding of each of the one or more blocks.

2. The computer-implemented method of claim 1, wherein the latent variables comprise row latent variables associated with the rows and column latent variables associated with the columns.

3. The computer-implemented method of claim 1, wherein the latent variables are estimated utilizing a spectral clustering algorithm.

4. The computer-implemented method of claim 1, wherein the latent variables are estimated using side information.

5. The computer-implemented method of claim 4, wherein the side information comprises a column datatype, a column name, or a row name.

6. The computer-implemented method of claim 1, further comprising, prior to (b), reordering the rows and columns of the structured data or semi-structured data based at least in part on the latent variables.

7. The computer-implemented method of claim 1, further comprising, prior to (c), generating a serialized block vector for each of the one or more blocks.

8. Computer-implemented method of claim 7, wherein the sequential encoding algorithm is applied to each serialized block vector.

9. The computer-implemented method of claim 8, wherein applying the sequential encoding algorithm comprises applying a first base compressor to each serialized block vector and a second base compressor to a latent variables of each serialized block vector.

10. The computer-implemented method of claim 9, wherein the first base compressor and the second base compressor are different.

11. The computer-implemented method of claim 1, wherein the structured data or semi-structured data is associated with hyperspectral imaging, image processing, quantum chemistry, or large language models.

12. The computer-implemented method of claim 1, wherein the structured data or semi-structured data is associated with tabular data.

13. The computer-implemented method of claim 1, wherein the method achieves an optimal compression rate.

14. The computer-implemented method of claim 1, wherein the method reduces a compression rate by at least about 5% compared to frequency-based entropy encoders (ANS), Lempel-Ziv encoders, or finite-state encoders.

15. A non-transitory computer readable medium comprising machine executable code that, upon execution by one or more computer processors, implements a lossless compression algorithm, comprising: (a) estimating latent variables associated with rows or columns of a structured data or semi-structured data; (b) partitioning the structured data or semi-structured data into one or more blocks according to the latent variables; (c) applying a sequential encoding algorithm to each of the one or more blocks; and (d) appending a compressed encoding of the latent variables to the compressed encoding of each of the one or more blocks.

16. The non-transitory computer readable medium of claim 15, wherein the latent variables comprise row latent variables associated with the rows and column latent variables associated with the columns.

17. The non-transitory computer readable medium of claim 15, wherein the latent variables are estimated utilizing a spectral clustering algorithm.

18. The non-transitory computer readable medium of claim 15, wherein the latent variables are estimated using side information.

19. The non-transitory computer readable medium of claim 18, wherein the side information comprises a column datatype, a column name, or a row name.

20. A computer program product for compressing structured data or semi-structured data, the computer program product comprising at least one non-transitory computer-readable medium having computer-readable program code portions embodied therein, the computer-readable program code portions comprising: an executable portion configured to estimate variables associated with rows or columns of the structured data or semi-structured data; an executable portion configured to partition the structured data or the semi-structured data into one or more blocks according to the latent variables; an executable portion configured to apply a sequential encoding algorithm to each of the one or more blocks; and an executable portion configured to append a compressed encoding of the latent variables to the compressed encoding of each of the one or more blocks.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The novel features of the invention are set forth with particularity in the appended claims. A better understanding of the features and advantages of the present invention will be obtained by reference to the following detailed description that sets forth illustrative embodiments, in which the principles of the invention are utilized, and the accompanying drawings (also figure and FIG. herein), of which:

(2) FIG. 1 shows an example of a spectral clustering algorithm in the pseudo-code for estimating spectral latents, in accordance with some embodiments;

(3) FIG. 2 shows an example of data reduction rate (DRR) using different datasets achieved by classical and latent-based compressors on real tabular data, in accordance with some embodiments. Datasets included Facebook (FB) Networks 1, 2, and 3, GP Network 1, Forest, Card Transactions, Business price index, US census, and Jokes. LZ refers to row-major order ZSTD, LZ (c) refers to column-major order ZSTD. KMeans was run on the data 5 times with random initializations finding the DRR each time and reporting the average. Datasets marked with(s) had rows randomly permuted (e.g., shuffled) before compressing. ZSTD generally refers to a Zstandard fast compression algorithm or method;

(4) FIG. 3A shows a comparison of data reduction rate (DRR) of naive ZSTD coding and latent-based ZSTD coding for synthetically generated data, in accordance with some embodiments. ZSTD generally refers to a Zstandard fast compression algorithm or method;

(5) FIG. 3B shows comparison of data reduction rate (DRR) of naive ANS coding and latent-based asymmetric numeral systems (ANS) coding for synthetically generated data. Contour lines correspond to the information-theoretically optimal compression rate, in accordance with some embodiments;

(6) FIG. 4 shows an example of Lempel-Ziv algorithm, in accordance with some embodiments;

(7) FIG. 5 shows a computer system that is programmed or otherwise configured to implement methods and algorithms provided herein, in accordance with some embodiments; and

(8) FIGS. 6-7 show an example of partitioning a table into blocks according to the latent variables, in accordance with some embodiments.

DETAILED DESCRIPTION

(9) The present disclosure provides improved methods for compressing structured data or semi-structured data. In some embodiments, the method comprises (a) estimating latent variables associated with rows or columns of the structured data or semi-structured data. In some embodiments, the method comprises (b) partitioning the structured data or the semi-structured data into one or more blocks according to the latent variables. In some embodiments, the method comprises (c) applying a sequential encoding algorithm to each of the one or more blocks. In some embodiments, the method comprises (d) appending a compressed encoding of the latent variables to the compressed encoding of each of the one or more blocks.

(10) Overview

(11) Data in structured or semi-structured format, which can be used for analytics and machine learning, may take the form of tables with, e.g., categorical or numerical entries. An unmet need exists for an improved lossless compression algorithm particularly for structured data or semi-structured data. The present disclosure provides systems and methods, which can improve the lossless compression performance over other methods or algorithms.

(12) For example, the present disclosure provides a probabilistic model to identify optimal compression for data, e.g., structured or tabular data. In some cases, latent values can be independent and table entries can be conditionally independent given the latent values. The probabilistic model can be characterized with a well-defined entropy rate to determine the ideal compression rate and to satisfy an asymptotic equipartition property. By applying the probabilistic model to different datasets, the latent estimation approach disclosed herein can achieve the optimal rate. In contrast, other compression methods, e.g., Lempel-Ziv or finite-state encoders, may not be able to achieve the optimal rate.

(13) In some cases, latent variables can be used in data compression methods based on machine learning and probabilistic modeling. Generally, latent variables in statistical models can include random variables that are unmeasured but may be unmeasurable. Latent variables can be included in statistical models for, in some cases, (1) including in the model features of interest that may not be directly measurable or were not measured; (2) constructing estimators that may be more efficient than those constructed from nonlatent variables models; and (3) constructing estimators of manipulation statistics that are unbiased.

(14) For example, stochastically generated codewords (e.g., random latents) can lead to minimum description lengths via bits back coding. This method can be explicitly applied to lossless data compression using arithmetic coding or ANS coding. For example, data compression via low-rank approximation or latents-based approaches can be applied to numerical analysis applications, hyperspectral imaging, image processing (2D or 3D), quantum chemistry, large language or machine learning models, artificial intelligence (AI) models, audio processing, cryptography, genetics or genome data, and the like. However, some latents-based approaches may mainly center on lossy compression and do not precisely quantify compression rate, e.g., they do not count bits.

(15) The present disclosure can provide an improvement in lossless compression rate over other methods. For example, the present disclosure provides a family of lossless compression algorithms for data, e.g., structured or semi-structured data. In some embodiments, the methods herein may comprise: (i) estimating latent variables associated to rows and columns of the table; (ii) partitioning the table in blocks according to the row or column latents; (iii) applyig a sequential encoding algorithm (e.g., Lempel-Ziv compression or entropy coding) to each of the blocks; and (iv) appending a compressed encoding of the latent. Evaluation of the methods on several bench-mark datasets show that latent estimation and row or column reordering can improve compression rate.

(16) In some cases, methods disclosed herein can improve upon mathematical algorithms, e.g., in compressing tabular data, by providing an asymptotically optimal algorithm that overcomes technical problems of other methods or algorithms. The lossless compression algorithms disclosed herein may be applied to various types of documents or data such as documents or data having comma-separated values (CSV) data, tab-separated values (TSV) data, Apache Parquet data, Apache optimized row columnar (ORC) data, Apache Feather data, Microsoft Excel (XLS) data, and the like. In some cases, the lossless compression algorithms disclosed herein may be applied to a document comprising semi-structured data (e.g., XML documents, JSON files, NoSQL databases, HTML code, graphs and tables, emails, etc.) or structured data (e.g., tabular data).

(17) 1 Introduction

(18) Some methods of lossless compression may assume that data takes the form of a random vector X.sup.N=(X.sub.1, X.sub.2, . . . , X.sub.N) of length N with entries in a finite alphabet X. Under suitable ergodicity assumptions and using the Shannon-McMillan-Breiman theorem, the entropy per letter may converge to a limit as h:=lim.sub.N.fwdarw.(X.sup.N)/N. Universal coding schemes (e.g., Lempel-Ziv coding) may not require knowledge of the distribution of X.sup.N and can encode such a sequence without information loss using (e.g., asymptotically) h bits per symbol. While this theory is mathematically useful, its modeling assumptions (e.g., stationarity, ergodicity, asymptotia, and the like) may not be satisfied by actual data in many applications.

(19) For example, consider a data table with m rows and n columns and entries in , :=. An approach to such data can include: (i) serializing, e.g., in row-first order, to form a vector of length N=, X.sup.N=(X.sub.11, X.sub.12, . . . , X.sub.in, X.sub.21, . . . , ) and (ii) applying a standard compressor (e.g., Lempel-Ziv) to this vector.

(20) It can be shown, both empirically and mathematically, that such an approach can be suboptimal in the sense of not achieving the optimal compression rate, e.g., data reduction rate (DRR). This can happen even in the limit of large tables, as long as the number of columns and rows are polynomially related (e.g., ) for some small constant & and large constant M).

(21) The present disclosure provides improved methods for compressing structured data or semi-structured data. In some cases, the method may use the following general scheme of operations 1, 2, and 3:

(22) 1. Estimating row latents =(u.sub.1, . . . , u.sub.m) and column latents =(v.sub.1, . . . , v.sub.n) , with , a finite alphabet. For example, FIGS. 6-7 illustrate an example of applying the method to structured data in, e.g., a table. As illustrated in FIG. 6, latents 620, including the row latents and column latents, are computed 611 for the structured data, e.g., table 610. In some cases, the method may implement latents estimation using a spectral clustering algorithm or using side information, described herein elsewhere. Side information can include: columns datatype, column names, row names, and the like.

(23) 2. Partitioning the table in blocks according to the row or column latents. For example, for each pair of latents values , , let R(u) be the subset of rows with latent value =u and C(v) be the subset of columns with latent value =v. Construct the table X_M (u, v) comprising the rows R (u) and columns C (v), in the same order as they appear in the original table. Then construct the vector or sequence X (u, v) by serializing X_M (u, v). In some cases, serializing the table may comprise scanning the entries of X_M (u, v) in row-first order or in column-first order. This operation can be performed by:

(24) $\begin{array}{cc}X\left(u,v\right)=\mathrm{vec}\left(X_{ij}:u_i=u,v_j=v\right)& \left(\mathrm{Eq}.1.1\right)\end{array}$
where vec (M) denote the serialization of matrix M (either row-wise or column-wise).

(25) As illustrated in FIG. 6, constructing the table X_M (u, v) may include reordering rows 621 and columns 621 of the table 620 based on the latents to obtain a reordered table 630. Then, the reordered table 630 can be partitioned into blocks 631 based on the latents. For example, as illustrated in FIG. 7, the blocks may be partitioned based on the latent values. In some cases, the blocks may have variable sizes based on the reordered values of the latent variables. Next, the partitioned blocks in the table 640 may be serialized 641 to generate a plurality of vectors 650. Each vector may correspond to a block or be referred to as a serialized block vector X (u, v).

(26) 3. Applying a base compressor, which can be generically denoted by Zx: .fwdarw.{0, 1}*, to each block X (u, v):

(27) $\begin{array}{cc}z\left(u,v\right)=Z_{}\left(X\left(u,v\right)\right),u,v& \left(\mathrm{Eq}.1.2\right)\end{array}$

(28) 4. Encoding the row latents and column latents using a possibly different compressor : *.fwdarw.{0,1} *, to get z.sub.row=Z.sub.L(), Z.sub.col=(). For example, as illustrated in FIG. 7, in the sequence compression 651, a base compressor such as sequence compression can be applied to the block vectors 651, and a compressor, which can be different than the base compressor, can be applied to the latents to obtain a plurality of compressed vectors 660. Considerations for selecting the base compressors are described herein elsewhere. Then, output the concatenation of all the above as:

(29) $\begin{array}{cc}Enc\left(X^{m,n}\right)=\mathrm{header}{z}_{row}{z}_{\mathrm{col}}{}_{u,v}z\left(u,v\right)& \left(\mathrm{Eq}.1.3\right)\end{array}$
where denotes concatenation, and header is a header that contains encodings of the lengths of subsequent segments (e.g., ||.sup.2+2 integers). The compressed vectors 660 may then be serialized 661 or concatenated to form a final vector 670.

(30) In some cases, encoding the latents can lead to a suboptimal compression rate. For example, techniques such as bits-back coding can merely yield limited improvement towards obtaining an optimal compression rate. It can be shown that the compression rate improvement achieved by such bits-back coding may only significant in certain special regimes, which is described herein elsewhere.

(31) In some cases, methods described herein can leave several design choices undefined. For example, design choices can include: (1) the latents estimation procedure; (2) the base compressor Z.sub.x for the blocks X(, ); or (3) the base compressor , for the latents. Implementation alongside empirical evaluation is described herein elsewhere.

(32) 2 Implementation

(33) 2.1 Base compressors

(34) Dictionary-based compression (LZ). As an example, Zstandard (ZSTD) can be used in its Python implementation. ZSTD can implement a Lempel-Ziv style algorithm.

(35) Frequency-based entropy coding (ANS). For each data portion (e.g., each block X(, ) and each of the row latents and column latents ), compute empirical frequencies of the corresponding symbols. For example, for all , , , compute:

(36) $\stackrel{}{Q}\left(x|u,v\right):=\frac{1}{N\left(u,v\right)}\underset{i:u_i=u}{.Math.}\underset{j:v_j=v}{.Math.}{1}_{x_{ij}=x}$$\stackrel{}{r}\left(u\right):=\frac{1}{m}{.Math.}_{i=1}^m{1}_{u_i=u},\mathrm{and}$
where N(, ) is the number of im, jn such that =u, =v. Apply ANS coding to each block X (u, v), modeling its entries as independent with distribution {circumflex over (Q)}(.Math.|u, v), to the row latents using the distribution {circumflex over (r)} (.Math.), and to the column latents using the distribution (.Math.). Separately encode these counts as long integers and prepend them to the file. In some cases, they can be a negligible fraction of the file size.
2.2 Latent Estimation

(37) In some cases, the method implements latents estimation using a spectral clustering algorithm. In some cases, the latents may be estimated using side information. Side information can include columns datatype, column names, row names, and the like. FIG. 1 shows an example of a spectral clustering algorithm in the pseudo-code.

(38) In some cases, the algorithm may encode the data matrix as an real-valued matrix using a map : .fwdarw.. In some cases, this map may not be optimized. In some cases, the elements of can be arbitrarily encoded as 0, 1, . . . ||1.

(39) In some cases, the singular vector calculation can be the most time consuming part of the algorithm. Computing approximate singular vectors via power iteration can require at least log (m{circumflex over ()}n) matrix vector multiplications for each of k vectors. This can amount to mnk log (m{circumflex over ()}n) operations, which can be larger than the time needed to compress the blocks or to run KMeans. The methods disclosed herein can improve this to (mVn) klog (mVn) n) via subsampling operations, which are described herein elsewhere.

(40) In some cases, for the spectral clustering operations, the method may use KMeans with k clusters, initialized randomly. For example, the algorithm may use the scikit-learn implementation via sklearn.cluster.KMeans. In some cases, the overall latent estimation approach may not estimate or make use of the model Q(.Math.|u, v). In some cases, an alternative approach based on an expectation-maximization (EM) algorithm may use such an estimation.

(41) 3 Empirical Evaluation

(42) Methods disclosed herein were evaluated on tabular datasets with different origins described below. The evaluation can be used to assess the impact of using latents in reordering columns and rows. In some cases, the evaluation may not attempt to achieve the best possible data reduction rate (DRR) on each dataset but rather to compare compression with latents and without latents. In some cases, the evaluation processed categorical variables by preprocessing the data to fit in this setting as described herein elsewhere. In some cases, the preprocessing included dropping some of the columns of the original table. The number of columns before preprocessing is denoted by , and after by . Differences between the implementation used in the evaluation and the methods described herein elsewhere are conceptually minor but can be practically important. Differences included: using different sizes for rows latent alphabet and column latent alphabet |||| and choosing ||, || by optimizing compression size.

(43) 3.1 Datasets

(44) The following datasets were utilized in the evaluation: taxicab, network, card transactions, business price index, forest, US census, and jokes.

(45) Taxicab. This table has =62, 495 rows, =20 columns comprising data for taxi rides in New York City during January 2022. After preprocessing, this table had =18 columns. For the LZ (ZSTD) compressor, 9 row latents were used. For the ANS compressor, 8 row latents were used. Both methods used column latents with each column compressed separately.

(46) Network. Four social networks from Stanford Network Analysis Platform (SNAP) Datasets, representing either friends as undirected edges for Facebook (FB) or directed following relationships on Google Plus (GP). It regards these as four distinct tables with 0-1 entries, with dimensions, respectively ={333, 747, 786, 1187}. For each table, the evaluation used 5 row latents and 5 column latents.

(47) Card transactions. A table of simulated credit card transactions containing information like card ID, merchant city, zip code, etc. This table has =24,386,900 rows and =15 columns. After preprocessing, the table had =12 columns. For this table, the evaluation used 3 row latents and n column latents.

(48) Business price index. A table of the values of the consumer price index of various goods in New Zealand between 1996 and 2022. This table has =72,750 rows and =12 columns from the Business price indexes: March 2022 quarter-CSV file. After preprocessing, this table had n=10 columns. Due to the highly correlated nature of consecutive rows, the data was shuffled before compressing. For the LZ method, the evaluation used 4 row latents. For the ANS method, the evaluation used 7 row latents. Both methods used column latents with each column compressed separately.

(49) Forest. This table from the UC Irvine (UCI) Machine Learning Repository has =581,011 cartographic measurements with =55 attributes, to predict forest cover type based on information gathered from US Geological Survey. The data contained binary qualitative variables and some continuous values like elevation and slope. After preprocessing, this data had =55 columns. For the LZ method, the evaluation used 9 row latents. For the ANS method, the evaluation used 8 row latents. Both methods used n column latents with each column compressed separately

(50) US Census. This table from the UCI Machine Learning Repository has =2,458,285 and =68 categorical attributes related to demographic information, income, and occupation information. After preprocessing, this data had =68 columns. For this data, the evaluation used 9 row latents and n column latents.

(51) Jokes. A table containing ratings of a series of jokes by 24,983 users collected between April 1999-May 2003. These ratings are real numbers on a scale from 10 to 10, and a value of 99 is given to jokes that were not rated. This table has =23,983 rows and =101. The first column identifies how many jokes were rated by a user, and the rest of the columns contain the ratings. After preprocessing, this data had =101 columns, all quantized. For the LZ method, the evaluation used 2 row latents. For the ANS method, the evaluation used 5 row latents. Both methods used n column latents.

(52) 3.2 Preprocessing

(53) Methods disclosed herein may preprocess different columns as follows: if a column comprises K256 unique values, then it maps the values to {0, . . . ,K1}; if a column is numerical and comprises more than 256 unique values, the method may calculate the quartiles for the data and map each entry to its quartile membership (e.g., 0 for the lowest quartile, 1 for the next largest, 2 for the next, and 3 for the largest); and if a column does not meet either of the above criteria, it may be discarded.

(54) In some evaluations, the data was randomly permuted before compression because some of the above datasets had rows already ordered in a way that can make nearby rows highly correlated.

(55) 3.3 Results

(56) Given a lossless encoder : .fwdarw.{0,1} *, its compression rate and data reduction rate (DRR) can be defined as:

(57) $\begin{array}{cc}{R}_{}\left(X^{m,n}\right):=\frac{\mathrm{len}\left(\left(X^{m,n}\right)\right)}{\mathrm{mn}{\log }_2.Math..Math.},DR{R}_{}\left(X^{m,n}\right):=1-R_{}\left(X^{m,n}\right)& \left(\mathrm{Eq}.3.1\right)\end{array}$
where larger DRR generally means better compression.

(58) The DRR of each algorithm is illustrated in FIG. 2. Datasets included datasets described herein elsewhere, e.g., taxicab, network, card transactions, business price index, forest, US census, and jokes. For the table of results in FIG. 2, LZ refers to row-major order ZSTD, LZ (c) refers to column-major order ZSTD. KMeans was run on the data 5 times, with random initializations finding the DRR each time, and reporting the average. Data marked with (s) had rows randomly permuted (e.g., shuffled) before compressing. ZSTD generally refers to a Zstandard fast compression algorithm or method.

(59) The results in FIG. 2 show that: (1) Latent+ANS encoders can achieve systematically the best DRR; (2) the use of latents in several cases can yield a DRR improvement of at least about 5% of the uncompressed size; and (3) this improvement is larger for data with a large number of columns, e.g., the network data of FB Network 1, FB Network 2, FB Network 3, and GP Network 1.

(60) 4 a Probabilistic Model

(61) In order to better understand the technical problems of other approaches and the improved optimality of latent-based compression, the presented disclosure provides a probabilistic model for the table . The model assumes the true latents ().sub.im, to be independent random variables with:

(62) $\begin{array}{cc}\left(u_i=u\right)=r\left(u\right),\left(v_i=v\right)=c\left(v\right)& \left(\mathrm{Eq}.4.1\right)\end{array}$

(63) Also, the model assumes that the entries , are conditionally independent given =().sub.im, =().sub.jn, with:

(64) $\begin{array}{cc}\left(X_{ij}=x|u^m,v^n\right)=Q\left(x|u_i,v_j\right)& \left(\mathrm{Eq}.4.2\right)\end{array}$

(65) The distributions r, c, and conditional distribution Q are parameters of the model with a total of 2(||1)+||.sup.2(||1) real parameters. In some cases, (X.sup.m,n, , )(Q, r, c; , ) can indicate that the triple (, , ) is distributed according to the probabilistic model, occasionally omits a subset of the variables, and thus results as ()(Q,r,c; ,). In some cases, the statements may be non-asymptotic, in which case , , , , Q, r, c can be fixed. In some cases, the statements may be asymptotic, in which case a sequence of problems can be indexed by .

(66) FIG. 3A shows a comparison of data reduction rate (DRR) of naive ZSTD coding and latent-based ZSTD coding for synthetically generated data. Contour lines correspond to the information-theoretically optimal compression rate.

(67) As an example of Symmetric Binary Model (SBM), the following SBM can be used, which parallels the symmetric stochastic block model for community detection. For example, take =[k]: ={1, . . . , k}, ={0,1}, r=c=Unif ([k]), the uniform distribution over [k], and

(68) $\begin{array}{cc}Q\left(1|u,v\right)=\{\begin{array}{cc}{p}_1& \mathrm{if}u=v\\ p_0& \mathrm{if}uv\end{array}& \left(\mathrm{Eq}.4.3\right)\end{array}$ where (X.sup.m,n, , )(, , k; , ) when this distribution is used.

(69) FIG. 3A and FIG. 3B show the results of simulations within this model, respectively for ZSTD-based. In this case ==1000, k=3, and DRR values are averaged over 4 realizations. In some cases, the use of latents can be irrelevant along the line p.sub.1p.sub.0, which may not impact the distribution of X.sub.ij. In some cases, the use of latents can become important when p.sub.1 and p.sub.0 are significantly different. FIG. 3B shows comparison of data reduction rate (DRR) of naive ANS coding and latent-based ANS coding for synthetically generated data. Contour lines correspond to the information-theoretically optimal compression rate.

(70) 5 Theoretical analysis

(71) 5.1 Ideal Compression

(72) Lemma 5.1. A first theorem or lemma can provide upper and lower bounds on the entropy per symbol H ()/. The first lemma 5.1 can be shown as:

(73) $\begin{array}{cc}& \left(\mathrm{Eq}.5.1\right)\end{array}$$H\left(X|U,V\right)\frac{1}{mn}H\left(X^{m,n}\right)H\left(X|U,V\right)+\frac{1}{n}H\left(U\right)+\frac{1}{m}H\left(V\right)$

(74) Further, for any estimators : .fwdarw., : .fwdarw.let

(75) 0${\hat{A}}_U:={\min }_{}{.Math.}_{i=1}^m{1}_{{\hat{u}}_i\left(u_i\right)}/m,{\hat{A}}_V:={\min }_{}{.Math.}_{i=1}^n{1}_{{\hat{v}}_i=\left(v_i\right)}/n$
(the minimum is over permutations of the letters in ). Letting .sub.U: =.sub.U, .sub.V:=.sub.V, the formula becomes:

(76) $\begin{array}{cc}H\left(X|U,V\right)+\frac{1}{n}H\left(U\right)+\frac{1}{m}H\left(V\right)-{}_{m,n}\frac{1}{mn}H\left(X^{m,n}\right)H\left(X|U,V\right)+\frac{1}{n}H\left(U\right)+\frac{1}{m}H\left(V\right){}_{m,n}:=\frac{1}{n}\left[h\left({}_U\right)+{}_u\log \left(.Math..Math.-1\right)\right]+\frac{1}{m}\left[h\left({}_V\right)+{}_V\log \left(.Math..Math.-1\right)\right]& \left(\mathrm{Eq}.5.2\right)\end{array}$

(77) Corollary 5.2. Recall the definition of compression rate from Eq. 3.1. Then, there may exist a lossless compressor such that:

(78) $\begin{array}{cc}& \left(\mathrm{Eq}.5.3\right)\end{array}$$R_{}\left(X^{m,n}\right)\frac{1}{{\log }_2.Math..Math.}\left\{H\left(X|U,V\right)+\frac{1}{n}H\left(U\right)+\frac{1}{m}H\left(V\right)+\frac{1}{mn}\right\}$

(79) Further, for any lossless compressor , R.sub.()H(X|U,V)+H(U)/)+H()/m.sub.m,n2 log.sub.2()/.

(80) The simpler bound of Eq. 5.1 may imply that the entropy per entry is H(X|U, V)+0(1/)). The operational interpretation of this result can be that it should be able to achieve the same compression rate per symbol as if the latents were given.

(81) The additional terms

(82) $\frac{1}{n}H\left(U\right)+\frac{1}{m}H\left(V\right)$
in Eq. 5.2 can account for the additional memory required for the latents. The lower bound in Eq. 5.2 may imply that, if the latents can be accurately estimated from the data (e.g., if .sub.U, .sub.v are small), then this overhead can be essentially or substantially unavoidable.

(83) The nearly ideal compression rate in Eq. 5.3 can be achieved by Huffmann or arithmetic coding, which may require knowledge of the probability distribution of . Under these schemes, the length of the codeword associated to is within a constant number of bits from log.sub.2P(), where P(X.sub.0):=(=X.sub.0) is the probability mass function of the random table . The next lemma 5.3 may imply that the length concentrates tightly around the entropy.

(84) Lemma 5.3. Asymptotic Equipartition Property. For X.sub.0, let P(X.sub.0)=(X.sub.0) the probability of X.sup.m,n=X, under model X.sup.m,n(Q,r, c; , ). Assume there exists a constant c>0 such that Q (x|u, v)c. Then, there can exist a constant C, which can depend on c, such that the following can happen: for (Q,r, c; , ) and any t0 with probability at least 12e.sup.t:

(85) $\begin{array}{cc}.Math.-\log P\left(X^{m,n}\right).Math.C\sqrt{mn\left(m+n\right)}t& \left(\mathrm{Eq}.5.4\right)\end{array}$

(86) For simplicity, in the last statement, assumptions can be made that are appropriate to the case, in which Q, r, c may be independent of ,. A more general statement with stronger, e.g., more complicate, bounds is described herein elsewhere.

(87) 5.2 Failure of Classical Compression Schemes

(88) Two types of codes are analyzed herein: finite-state encoders and Lempel-Ziv codes. Both can operate on the serialized data X.sup.N=vec(X.sup.m,n), N=, which can be obtained by scanning the table in row-first order where column-first can yield symmetric results.

(89) 5.2.1 Finite state encoders. A finite state (FS) encoder can take the form of a triple (, f, g) with a finite set of cardinality M=|| and

(90) $\begin{array}{cc}f:.Math..fwdarw.{\left\{0,1\right\}}^{*},g:.Math..fwdarw..Math.& \left(\mathrm{Eq}.5.5\right)\end{array}$

(91) Assume that contains a special initialization symbol s.sub.init. Starting from state s.sub.0=s.sub.init, the encoder can scan the input X.sup.N sequentially. Assume after the first input symbols, the state is in state and produced encoding . Given input symbol , the encoder appends f(() to the codeword and updates its state to =g(, ).

(92) Denote (, s.sub.init){0,1} *, the binary sequence obtained by applying the finite state encoder to the vector =(X.sub.1, . . . , ). The FS encoder can be defined as information lossless if for any , (, s.sub.init) is injective.

(93) Theorem 1. Let (Q, r, c; , ) and (, f, g) be an information lossless finite state encoder. Define the corresponding compression rate R.sub.,f,g(), as per Eq. 3.1. Assuming >10, |||, and log.sub.2|||X |/9, then,

(94) $\begin{array}{cc}{R}_{,f,g}\left(X^{m,n}\right)\frac{H\left(X|U\right)}{{\log }_2.Math..Math.}-10\sqrt{\frac{\log .Math..Math.}{n\log .Math..Math.}}\log \left(n\log .Math..Math.\right)& \left(\mathrm{Eq}.5.6\right)\end{array}$
where the leading term of the above lower bound is H(X|U)/log.sub.2|X|.

(95) Since conditioning can reduce entropy, this is strictly larger than the ideal rate which is roughly H(X|U,V)/log.sub.2|X|, e.g., Eq. 5.3. The next term can be negligible provided log||<<n log|X|, e.g., modulo logarithmic factors which may be a proof artifact. This condition can be easy to interpret. For example, the finite state machine may not have enough states to memorize a row.

(96) 5.2.2 Lempel-Ziv

(97) The pseudocode of the Lempel-Ziv algorithm is shown in FIG. 4. FIG. 4 shows that, after the first k characters of the input have been parsed, the encoder can find the longest string

(98) $X_k^{k+-1},$
which may appear in the past. The encoder can then encode a pointer to the position of the earlier k appearance of the string T.sub.k and its length L.sub.k.

(99) The method can then encode the pointer T.sub.k in plain binary using [log.sub.2 (N+|x|)]bite. In some cases, T.sub.k {|X|+1, . . . , 1, . . . , N}), and Ly can use an instantaneous prefix-free code, e.g., Elias -code, taking 2 [log.sub.2L.sub.k]+1. This can be sub-optimal, but the space taken by the encoding of L.sub.k can be of lower order with respect to the one of T.sub.k

(100) Assumption 1. The following can hold:

(101) 1. There exist a constant c.sub.o>0 such that:

(102) $\begin{array}{cc}\underset{x}{\max }\underset{u,v}{\max }Q\left(x.Math.u,v\right)1-c_0& \left(\mathrm{Eq}.5.7\right)\end{array}$

(103) 2. Consider sequences of instances with Q r, c, X, fixed and m, n=.fwdarw. so that:

(104) $\begin{array}{cc}\underset{n.fwdarw.}{\lim }\frac{\log m}{\log n}=\left(0,\right)& \left(\mathrm{Eq}.5.8\right)\end{array}$
equivalently =

(105) As mentioned herein, consider sequences of instances with ,.fwdarw., which can mean the sequence to be indexed by , and let =, which can depend on such that Eq. 5.8 holds.

(106) Theorem 2. Define the asymptotic Lempel-Ziv rate as:

(107) 0$\begin{array}{cc}{R}_{LZ}^{}:=\frac{1}{{\log }_2.Math.X.Math.}{.Math.}_{u}r\left(u\right)\left[H\left(X.Math.U=u\right)\left(\frac{1+}{}\right)H\left(X.Math.U=u,.Math.V\right)\right]& \left(\mathrm{Eq}.5.9\right)\end{array}$ Then, under Assumption 1,

(108) $\begin{array}{cc}\underset{m,n.fwdarw.}{\lim }{R}_{LZ}\left(X^{m,n}\right)=R_{LZ}^{}& \left(\mathrm{Eq}.5.1\right)\end{array}$

(109) The asymptotics of the Lempel-Ziv rate can be given by the minimum of two expressions, which can correspond to different behaviors of the encoder. For example, for , define (): =H(X|U=, V)/(H(X|U=)H(X|U=, V)) with ()= if H(X|U=)=H(X|U=,V)).

(110) Then, if <.sub.*(), then it may be a skinny table regime. For example, the algorithm may mostly deduplicate segments in rows with latent u by using strings in different rows but aligned in the same columns. If <(), then it may be a fat table regime. For example, the algorithm may mostly deduplicate segments on rows with latent u by using rows and columns that are not the same as the current segment.

(111) Example. Symmetric Binary Model (SBM), dense regime. Under the SBM, (,,k;,) example, the optimal compression rate of Corollary 5.2, the finite state compression rate of Theorem 1, the Lempel-Ziv rate of Theorem 2 can be computed.

(112) Assume , of order one, and = as , .fwdarw.. In some cases, the resulting tales can be dense in the sense of containing a constant fraction of non-zeros. Then,

(113) $\begin{array}{cc}{R}_{\mathrm{opt}}\left(X^{m,n}\right)=\left(1-\frac{1}{k}\right)h\left(p_0\right)+\frac{1}{k}h\left(p_1\right)+o_n\left(1\right)& \left(\mathrm{Eq}.5.11\right)\end{array}$$\begin{array}{cc}{R}_{,f,g}\left(X^{m,n}\right)h\left(\stackrel{}{p}\right)+o_n\left(1\right),\stackrel{}{p}:=\left(1-{}^{\underset{\_}{1}}k\right)p_0+\frac{1}{k}{p}_1& \left(\mathrm{Eq}.5.12\right)\end{array}$$\begin{array}{cc}{R}_{LZ}\left(X^{m,n}\right)=h\left(\stackrel{}{p}\right)\left(\frac{1+}{}\right)\left(\left(1-\frac{1}{k}\right)h\left(p_0\right)+\frac{1}{k}h\left(p_1\right)\right)+o_n\left(1\right)& \left(\mathrm{Eq}.5.13\right)\end{array}$
where the right hand sides correspond to the contour lines in FIG. 3A and FIG. 3B and where ANS is a finite-state encoder.
5.3 Practical Latent-Based Compression

(114) Achieving the ideal compression rate of Corollary 5.2 via arithmetic or Huffmann coding may require, a priori, computing the probability P () of the table . The method herein can achieve a compression rate that is close to the ideal rate via latents estimation. For example, consider general latents estimators :.fwdarw., : .fwdarw.. Accuracy can be measured by the overlaps as:

(115) ${}_U\left(X;\hat{u}\right):=\frac{1}{m}\underset{}{\min }\underset{i=1}{\overset{m}{.Math.}}{1}_{{\hat{u}}_i}\left(X\right)\left(u_i\right)$${}_V\left(X\right):\stackrel{}{v}):=\frac{1}{n}\underset{}{\min }\underset{i=1}{\overset{n}{.Math.}}{1}_{{\hat{v}}_i}\left(X\right)\left(v_i\right)$
where the minimization is over the set of permutations of the latents alphabet .

(116) Any estimators , can be used to reorder rows and columns and compress the table according to the methods described herein. Denote by R.sub.lat (), the compression rate achieved by such a procedure. From Eq. 1.3, the following can be obtained:

(117) $\begin{array}{cc}{R}_{lat}\left(X^{m,n}\right)=\frac{1}{\mathrm{mn}{\log }_2.Math.X.Math.}\{\mathrm{len}\left(\mathrm{header}\right)+\mathrm{len}\left(Z_{}\left(\hat{u}\right)\right)+\mathrm{len}\left(Z_{}\left(\stackrel{}{v}\right)\right)+{.Math.}_{u,}\mathrm{len}\left(Z_{}.Math.\stackrel{}{X}\left(u,v\right)\right))\}& \left(\mathrm{Eq}.5.14\right)\end{array}$
where {circumflex over (X)}(, )=)=vec(X.sub.ij: (X)=(X)=v are the estimated blocks of X. This rate can depend on the base compressors , but can be omitted these from notations. The first result can imply that, if the latent estimators are consistent, e.g., they recover the true latents with high probability up to permutations, then the resulting rate may be close to the ideal one.

(118) Lemma 5.4. Assume data distributed according to model (Q, r, c; , ), with , log.sub.2||. Further, assume r(), c()>c for all , . Let R.sub.lat () be the rate achieved by the latent-based scheme with latents estimators , and base encoders ==Z. Then,

(119) $\begin{array}{cc}{R}_{lat}\left(X^{m,n}\right)\frac{H\left(X^{m,n}\right)}{\mathrm{mn}{\log }_2.Math.X.Math.}+2\left({\hat{A}}_U\left(X^{m,n};\hat{u}\right)<1\right)+2\left({\hat{A}}_V\left(X^{m,n};\stackrel{}{v}\right)<1\right)+\frac{4\log \left(mn\right)}{mn}+{.Math..Math.}^2{}_Z(c.Math.\mathrm{mn};{\left\{Q\left(.Math..Math.u,v\right)\right\}}_{u,v}+2{}_Z\left(mn;\left\{r,c\right\}\right)& \left(\mathrm{Eq}.5.15\right)\end{array}$
where .sub.z (N; *) can be the worst case overhead of encoder Z over sources with distributions in *.

(120) For example, the overheads of Lempel-Ziv, frequency-based arithmetic coding, and frequency-based ANS coding can be upper bounded respectively as (e.g., where the last bound requires Q,r,c to be independent of N):

(121) $\begin{array}{cc}{}_{\mathrm{LZ}}(N;\text{*)}\frac{C\left(\log {.Math..Math.}^2\right)}{\log N}& \left(\mathrm{Eq}.5.16\right)\end{array}$$\begin{array}{cc}{}_{\mathrm{AC}}(N;\text{*)}\frac{2.Math..Math.\left(\log N\right)}{N}& \left(\mathrm{Eq}.5.17\right)\end{array}$$\begin{array}{cc}{}_{\mathrm{ANS}}(N;\text{*)}\frac{2.Math..Math.(\log N+C_{\left|\right|}}{N}& \left(\mathrm{Eq}.5.18\right)\end{array}$

(122) The proof of this lemma and the main content of the lemma is in the general bound of Eq. 5.15. More explicitly, .sub.z (N; *) can be defined by:

(123) $\begin{array}{cc}{}_Z(N;\text{*)}:=\frac{1}{N{\log }_{2}k},\underset{p*}{\max }\left\{{}_p\mathrm{len}\left(Z\left(Y^N\right)\right)-H\left(Y^N\right)\right\}& \left(\mathrm{Eq}.5.19\right)\end{array}$
where ([k]): ={().sub.ik :0i.sub.ik =1} is the set of probability distributions over [k], and Y.sup.N is a vector with entries Y.sub.i. The upper bound (5.16) may be closely related to classical results.
A. Notations, Definition, and Basic Facts

(124) The data take form the form

(125) $X_1^n{X}^n,$
Where X is a finite alphabet. Consider lossless encoders E: X.sup.n.fwdarw.{0,1}.sup.*, and denote by

(126) $k\left(x_1^n;E\right)=\mathrm{len}\left(E\left(x_1^n\right)\right)$
the length of the encoded sequence on input .

(127) For ab, it uses

(128) 0$x_a^b=\left(x_a,.Math.,x_b\right)$
to denote the substring of x. Given a sequence , it denotes by

(129) ${\stackrel{}{p}}_k\left(.Math.;x_1^n\right)$
the empirical distribution of sequences of length k. Namely, for wcX.sup.k, let,

(130) ${\stackrel{}{p}}_k\left(w;x_1^n\right):=\frac{1}{n-k+1}\underset{i=1}{\overset{n-k+1}{.Math.}}{1}_{x_i^{i+k-1}=w}$

(131) The Shannon entropy of a probability distribution p over a finite or countable set Z is given by,

(132) $H\left(p\right)=-\underset{z}{.Math.}p\left(z\right){\log }_{2}p\left(z\right)$

(133) Denote by h() the entropy of a Bernoulli random variable Z with (Z=1)=1(Z=0)= by,

(134) $h\left(\right)=-{\log }_2-\left(1-\right){\log }_2\left(1-\right)$

(135) Lemma Let A be a finite set and F: A.fwdarw.{0, 1} * be an injective map. Then, for any probability distribution p over A

(136) $\underset{aA}{.Math.}p\left(a\right)\mathrm{len}\left(F\left(a\right)\right)H\left(p\right)-{\log }_2{\log }_2\left(.Math.A.Math.+2\right)$

(137) Proof. Assume without loss of generality that A={1, . . . , M}, with |A|=K, and that the elements of A have all non-vanishing probability and are ordered by decreasing probability p.sub.1p.sub.2 . . . p.sub.k>0. Let : =2+4+ . . . +=+1-2. Then the expected length is minimized any map F such that len(F())=for .sub.1a with the maximum length being defined by .sub.1<K. For A, L: =len(F(A)), then:

(138) $H\left(p\right):={H\left(A\right)}_{}^{\left(a\right)}H\left(L\right)+H\left(A|L\right){\log }_2{}_k+\underset{=1}{\overset{{}_k}{.Math.}}\left(L=\right)H\left(A|L=\right)\stackrel{\left(b\right)}{}{\log }_2{}_k+\underset{=1}{\overset{{}_M}{.Math.}}\left(L=\right){\log }_2{\log }_2\left(K+2\right)+\underset{aA}{.Math.}p\left(a\right)\mathrm{len}\left(F\left(a\right)\right)$
where (a) is the chain rule of entropy and (b) follows because by injectivity, given len(F(A))=, A can take at most values.
B Proofs of results on ideal compression
Proof of Lemma 5.1

(139) Claiming that:

(140) $\begin{array}{cc}\frac{1}{mn}H\left(X^{m,n}\right)=H\left(X|U,V\right)+\frac{1}{mn}I\left(X^{m,n},U^m,V^n\right)& \left(B\text{.1}\right)\end{array}$
by the definition of mutual information, obtain H()=H(|, )+I(|, ). Equation B.1 follows by noting that:

(141) $H\left(X^{m,n}|U^m,V^n\right)\underset{u{}^m}{.Math.}\underset{v{}^n}{.Math.}\left(U^m=u,V^n=v\right)H\left(X^{m,n}|U^m=u,V^n=v\right)\stackrel{\left(a\right)}{=}\underset{i=1}{\overset{m}{.Math.}}\underset{j=1}{\overset{n}{.Math.}}\underset{u}{.Math.}\underset{v{}^n}{.Math.}\left(U^m=,V^n=v\right)H\left(X_{i,j}|U_i=u,V_j=v\right)=\underset{i=1}{\overset{m}{.Math.}}\underset{j=1}{\overset{n}{.Math.}}\underset{u}{.Math.}\underset{v}{.Math.}\left(U_i=u_i,V_j=v_j\right)H\left(X_{i,j}|U_i=u_i,V_j=v_j\right)=\underset{i=1}{\overset{m}{.Math.}}\underset{j=1}{\overset{n}{.Math.}}H\left(X_{i,j}|U_i,V_j\right)\stackrel{\left(b\right)}{=}\mathrm{mnH}\left(X_{1,1}|U_1,V_1\right)$
where (a) follows from the fact that the (X.sub.i,j) are conditionally independent given U.sup.m, V.sup.n, ad since the conditional distribution of X.sub.i,j only depends on U.sup.m, V.sup.n via U.sub.i, V.sub.j; (b) holds because the triples (X.sub.i,j, U.sub.i, V.sub.j) are identically distributed.

(142) The lower bound in Eq. 5.1 holds because mutual information is non-negative, and the upper bound because I (, , )H (, )=+.

(143) Finally, Eq. 5.2 holds because

(144) $I\left(X^{m,n};U^m,V^n\right)=H\left(U^m,V^n\right)-H\left(U^m,V^n|X^{m,n}\right)mH\left(U_1\right)+nH\left(V_1\right)-\underset{i=1}{\overset{m}{.Math.}}H\left(U_i|X^{m,n}\right)-\underset{j=1}{\overset{n}{.Math.}}H\left(V_j|X^{m,n}\right)=mH\left(U_1\right)+nH\left(V_1\right)-mH\left(U_1|X^{m,n}\right)-nH\left(V_1|X^{m,n}\right)$
Proof of Lemma 5.3

(145) Lemma B.1. Let =, == be collections of mutually independent random variables taking values in a measurable space Z.x.Z.sup.3.fwdarw.Z, F: .fwdarw.. Define x(, , )via x(, , ).sub.ij=x (.sub.ij, .sub.i, .sub.j).

(146) Given a vector of independent random variables z, let Var.sub.zj(f(z)):=[(f(z)f(z)).sup.2]Define the quantities:

(147) 0$\begin{array}{cc}{B}_{*}:=\max .Math.F\left(x\right)-F\left(x^{}\right).Math.& \left(\mathrm{Eq}.B\text{.2}\right)\end{array}$$x,x^{}{}^{mn}$$d\left(x,x^{}\right)1$$B_1:=\max \max \left|{}_{}F\left(x\left(,,\right)\right)-{}_{}F\left(x\left(,{}^{},\right)\right)\right|$$\begin{array}{cc},{}^{}{}^m{}^n& \left(\mathrm{Eq}.B\text{.3}\right)\end{array}$$d\left(,{}^{}\right)1$$\begin{array}{cc}{B}_2:=\max \max \left|{}_{}F\left(x\left(,,\right)\right)-{}_{}F\left(x\left(,,{}^{}\right)\right)\right|& \left(\mathrm{Eq}.B\text{.4}\right)\end{array}$${}^m,{}^{}{}^n$$d\left(,{}^{}\right)1$$\begin{array}{cc}{V}_{*}:=\underset{,,}{\sup }{.Math.}_{im,jn}{\mathrm{Var}}_{{}_{ij}}\left\{F\left(x\left(,,T\right)\right)\right\}& \left(\mathrm{Eq}.B\text{.5}\right)\end{array}$$\begin{array}{cc}{V}_1:=\underset{,}{\sup }{.Math.}_{im}{\mathrm{Var}}_{{}_i}\left\{{}_{}F\left(x\left(,,\right)\right)\right\},& \left(\mathrm{Eq}.B\text{.6}\right)\end{array}$$\begin{array}{cc}{V}_2:=\underset{,}{\sup }{.Math.}_{jn}{\mathrm{Var}}_{{}_j}\left\{{}_{}F\left(x\left(,,\right)\right)\right\}& \left(\mathrm{Eq}.B\text{.7}\right)\end{array}$

(148) Then, for any t0, the following holds with probability at least 18e.sup.t:
|F(x(,,)F(x(,,)2 max(2V.sub.*t+2V.sub.1t+2V.sub.2t;(B.sub.*+B.sub.1+B.sub.2)t). (Eq. B.8)

(149) Proof. Let zZ.sup.N be a vector of independent random variables and f: Z.sup.N.fwdarw.. Define the Martingale X.sub.k: =[f(z)|] (where :=(Z.sub.1, . . . , Z.sub.k)). Then it follows:

(150) $\begin{array}{cc}\mathrm{ess}\sup .Math.X_k-X_{k-1}.Math.B_0:=\underset{d\left(x,z^{}\right)1}{\sup }.Math.f\left(z\right)-f\left(z^{}\right).Math.,& \left(\mathrm{Eq}.B\text{.9}\right)\end{array}$$\begin{array}{cc}{.Math.}_{k=1}^N\left[{\left(X_k-X_{k-1}\right)}^2|{}_{k-1}\right]=& \left(\mathrm{Eq}.B\text{.10}\right)\end{array}$${.Math.}_{k=1}^N\left[{\left(E\left[f|z_{<k},z_k\right]-{}_{z_k^{}}\left[f|z_{<k},z_k^{}\right]\right)}^2|z_{<k}\right]$$\begin{array}{cc}{V}_0:=\underset{z{}^N}{\sup }{.Math.}_{k=1}^N{\mathrm{Var}}_{z_k}\left(f\left(z\right)\right)& \left(\mathrm{Eq}.B\text{.11}\right)\end{array}$

(151) By Freedman's inequality, with probability at least 1-2e.sup.t, it follows:

(152) $\begin{array}{cc}.Math.f\left(z\right)-f\left(z\right).Math.\max \left(\sqrt{2V_{0}t}:\frac{2B_{0}t}{3}\right)& \left(\mathrm{Eq}.B\text{.12}\right)\end{array}$

(153) Define E(,):=F(x(, , )), L():=(x(, , )). Applying the above inequality, each of the following holds with probability at least 1-2e.sup.t:

(154) $\begin{array}{cc}.Math.F\left(x\left(,,\right)\right)-E\left(,\right).Math.\max \left(\sqrt{2V_{*}t}:\frac{2B_{*}t}{3}\right)& \left(\mathrm{Eq}.B\text{.13}\right)\end{array}$$\begin{array}{cc}.Math.E\left(,\right)-L\left(\right).Math.\max \left(\sqrt{2V_{1}t}:\frac{2B_{1}t}{3}\right)& \left(\mathrm{Eq}.B\text{.14}\right)\end{array}$$\begin{array}{cc}.Math.L\left(\right)-F\left(x\right).Math.\max \left(\sqrt{2V_{2}t}:\frac{2B_{2}t}{3}\right)& \left(\mathrm{Eq}.B\text{.15}\right)\end{array}$
and the claim follows by union bound.

(155) Following proves a more stronger version of Lemma 5.3.

(156) Lemma B.2. For X, let P(X)=(X) the probability applied by the model (Q, r, c; , ) to matrix X, i.e.,
P(X)=.sub.(i,j)[m][n]Q(X.sub.ij,)r().sub.j[n]c(.sub.)(Eq. B.16)

(157) Define the following quantities:

(158) $\begin{array}{cc}{M}_{*}:=\underset{x,x^{}X}{\max }\underset{u,v}{\max }.Math.\log \frac{Q\left(x|u,v\right)}{Q\left(x|u,v\right)}.Math.& \left(\mathrm{Eq}.B\text{.17}\right)\end{array}$$\begin{array}{cc}{M}_1:=\underset{,,{}^{}}{\max }{.Math.Q\left(.Math.|,\right)-Q\left(.Math.|{}^{},\right).Math.}_{TV}\underset{u,v,x,x^{}}{\max }.Math.\log \frac{Q\left(x|u,v\right)}{Q\left(x|u,v\right)}.Math.& \left(\mathrm{Eq}.B\text{.18}\right)\end{array}$$\begin{array}{cc}{M}_2:=\underset{,{}^{}.}{\max }{.Math.Q\left(.Math.|,\right)-Q\left(.Math.|,{}^{}\right).Math.}_{TV}\underset{u,v,x,x^{}}{\max }.Math.\log \frac{Q\left(x|u,v\right)}{Q\left(x|u,v\right)}.Math.& \left(\mathrm{Eq}.B\text{.19}\right)\end{array}$$\begin{array}{cc}& \left(\mathrm{Eq}.B\text{.20}\right)\end{array}$$s_{*}:=\frac{1}{2}\underset{u_0,v_0}{\max }{.Math.}_{x,x^{}X}Q\left(x|u_0{v}_0\right)Q\left(x^{}|u_0{v}_0\right){\underset{u,v}{\max }\left(\log \frac{Q\left(x|u,v\right)}{Q\left(x|u,v\right)}\right)}^2$$\begin{array}{cc}& \left(\mathrm{Eq}.B\text{.21}\right)\end{array}$$s_1:=\frac{1}{2}\underset{u_0,u_0^{}{v}_0}{\max }{.Math.Q\left(.Math.|u_0,v_0\right)-Q\left(.Math.|u_0,v_0\right).Math.}_{TV}\underset{x,x^{}}{\max }{\underset{u,v}{\max }\left(\log \frac{Q\left(x|u,v\right)}{Q\left(x|u,v\right)}\right)}^2$$\begin{array}{cc}& \left(\mathrm{Eq}.B\text{.22}\right)\end{array}$$s_2:=\frac{1}{2}\underset{u_0,v_0,v_0}{\max }{.Math.Q\left(.Math.|u_0,v_0\right)-Q\left(.Math.|u_0,v_0^{}\right).Math.}_{\mathrm{TV}}\underset{x,x^{}}{\max }{\underset{u,v}{\max }\left(\log \frac{Q\left(x|u,v\right)}{Q\left(x|u,v\right)}\right)}^2$

(159) Then, for X(Q, r, c; m, n) and any t0 the following bound holds with probability at least 2e.sup.t:

(160) $\begin{array}{cc}.Math.-\log P\left(X\right)-H\left(X\right).Math.3\max \left(\sqrt{s_{*}mnt}+\sqrt{s_{1}m{n}^{2}t}+\sqrt{s_2{m}^{2}nt},M_{*}+M_{1}n+M_{2}m\right)& \left(\mathrm{Eq}.B\text{.23}\right)\end{array}$

(161) Proof. Let

(162) $={\left({}_i\right)}_{im}{}_{iid}r,={\left({}_i\right)}_{in}{}_{iid}c,={\left({}_{ij}\right)}_{im,jn}{}_{iid}\mathrm{Unif}\left(\left[0,1\right]\right),\mathrm{and}x:\left[0,1\right].fwdarw.$
be such that x(.sub.ij, .sub.i, .sub.i)|.sub.i, .sub.iQ (.Math.|.sub.i; .sub.i). It defines F(x)=log P(x), and will apply Lemma B.1 to this function. Using the notation from that lemma, it claims that B.sub.*M.sub.*, B.sub.1M.sub.1, B.sub.2M.sub.2, and V , V.sub.1s.sub.1, V.sub.2s.sub.2.

(163) Note that, if (x.sub.ij), (x.sub.ij) differ only for entry i, j, then:

(164) $\begin{array}{cc}F\left(x\right)-F\left(x^{}\right)=-\log E_{u,v|x}\left\{\frac{Q\left(x_{ij}^{}|u_i,v_j\right)}{Q\left(x_{ij}|u_i,v_j\right)}\right\}& \left(\mathrm{Eq}.B\text{.24}\right)\end{array}$
where denotes expectation with respect to the posterior measure P(, |X=x). This immediately implies BM.

(165) Next consider the constant B.sub.1 defined in Eq. (B.3). Using the exchangeability of the (.sub.i,., .sub.i), it gets:

(166) $B_1=\underset{}{\max }.Math.{}_{}\log {}_{u,v|x}\left\{\stackrel{n}{\underset{j=1}{.Math.}}\frac{Q\left(x\left({}_{1,j,}{}_1^{},{}_j\right)|u_1,v_j\right)}{Q(x({}_{1,j,}{}_1,{}_j\left(|u_1,v_j\right)}\right\}.Math.\underset{}{\max }{}_{}\underset{u,v}{\max }.Math.\log \left\{\underset{j=1}{\overset{n}{.Math.}}\frac{Q\left(x\left({}_{1,j,}{}_1^{},{}_j\right)|u_1,v_j\right)}{Q\left(x\left({}_{1,j,}{}_1,{}_j\right)|u_1,v_j\right)}\right\}.Math.\underset{}{\max }\underset{j=1}{\overset{n}{.Math.}}{}_{}{\max }_{u,v}.Math.\log \left\{\frac{Q\left(x\left({}_{1,j,}{}_1^{},{}_j\right)|u_1,v_j\right)}{Q\left(x\left({}_{1,j,}{}_1,{}_j\right)|u_1,v_j\right)}\right\}.Math.n\underset{,{}^{}}{\max }{}_{}\underset{u,v}{\max }.Math.\log \frac{Q\left(x\left({}_1,{}_1^{},{}_j\right)|u_1,v_j\right)}{Q\left(x\left({}_1,{}_1,{}_j\right)|u_1,v_j\right)}.Math.n\underset{,{}^{}}{\max }{.Math.Q\left(.Math.|,\right)-Q\left(.Math.|{}^{},\right).Math.}_{\mathrm{TV}}\underset{u,v,x,x^{}}{\max }.Math.\log \frac{Q\left(x|u,v\right)}{Q\left(x^{}|u,v\right)}.Math.=M_1$
where the bound B.sub.2M.sub.2m is proved analogously.

(167) Consider now the quantity Va of Eq. (B.5). Denote by .sub.(ij)(t) the array obtained by replacing entry (i, j) in {by t, and by x (t)=x (.sub.(ij)(t), , ). Then it follows:

(168) ${\mathrm{Var}}_{{}_{ij}}\left(F\left(x\right)\right)=\frac{1}{2}{}_{{}^{},{}^{}}\left\{{\left(F\left(x\left({}_{\left(ij\right)}\left({}^{}\right),,\right)\right)-F\left(x\left({}_{\left(ij\right)}\left({}^{}\right),,\right)\right)\right)}^2\right\}=\frac{1}{2}{}_{{}^{},{}^{}}\left\{{\left(\log E_{u,v|x\left({}^{}\right)}\left\{\frac{Q\left(x\left({}^{},{}_i,{}_j\right)|u_i,v_j\right)}{Q\left(x\left({}^{},{}_i,{}_j\right)|u_i,v_j\right)}\right\}\right)}^2\right\}\frac{1}{2}{}_{{}^{},{}^{}}{\underset{u,v}{\max }\left(\log \left\{\frac{Q\left(x\left({}^{},{}_i,{}_j\right)|u_i,v_j\right)}{Q\left(x\left({}^{},{}_i,{}_j\right)|u_i,v_j\right)}\right\}\right)}^2=\frac{1}{2}\underset{x,x^{}}{.Math.}Q\left(x|,\right)Q\left(x^{}|,\right){\underset{u,v}{\max }\left(\log \left\{\frac{Q\left(x|u,v\right)}{Q\left(x^{}|u,v\right)}\right\}\right)}^2$

(169) Next, as claimed:

(170) 0$V_{*}\underset{,,}{\max }\underset{im,jn}{.Math.}{\mathrm{Var}}_{{}_{\mathrm{ij}}}\left\{F\left(x\right)\right\}\mathrm{mn}\underset{,,}{\max }{\mathrm{Var}}_{{}_{\mathrm{ij}}}\left\{F\left(x\right)\right\}{\mathrm{mns}}_{*}$

(171) Finally, consider the quantity V.sub.1 of Eq. (B.6) (the argument is similar for V.sub.2). Denote by .sub.(i)(t) the vector obtained by replacing entry i in by t. Proceeding as above, it follows:

(172) ${\mathrm{Var}}_{{}_i}\left({}_{}F\left(x\right)\right)=\frac{1}{2}{}_{{}^{},{}^{}}\left\{{\left({}_{}F\left(x\left(,{}_{\left(i\right)}\left({}^{}\right),\right)\right)-{}_{}F\left(x\left(,{}_{\left(i\right)},\right)\right)\right)}^2\right\}=\frac{1}{2}{}_{{}^{},{}^{}}\left\{{\left({}_{}\log E_{u,v|x\left({}^{}\right)}\left\{\underset{j=1}{\overset{n}{.Math.}}\frac{Q\left(x\left({}_{\mathrm{ij}},{}^{},{}_j\right)|u_i,v_j\right)}{Q\left(x\left({}_{\mathrm{ij}},{}^{},{}_j\right)|u_i,v_j\right)}\right\}\right)}^2\right\}\frac{1}{2}{}_{{}^{},{}^{}}\left\{{\left({}_{}\log \left\{\underset{j=1}{\overset{n}{.Math.}}\underset{u,v}{\max }\frac{Q\left(x\left({}_{\mathrm{ij}},{}^{},{}_j\right)|u_i,v_j\right)}{Q\left(x\left({}_{\mathrm{ij}},{}^{},{}_j\right)|u_i,v_j\right)}\right\}\right)}^2\right\}\frac{1}{2}{}_{{}^{},{}^{}}\left\{{\left(\underset{j=1}{\overset{n}{.Math.}}{}_{}\log \left\{\underset{u,v}{\max }\frac{Q\left(x\left(,{}^{},{}_j\right)|u,v\right)}{Q\left(x\left(,{}^{},{}_j\right)|u,v\right)}\right\}\right)}^2\right\}\frac{n^2}{2}\underset{}{\max }{}_{{}^{},{}^{}}\left\{{\left({}_{}\log \left\{\underset{u,v}{\max }\frac{Q\left(x\left(,{}^{},{}_j\right)|u,v\right)}{Q\left(x\left(,{}^{},{}_j\right)|u,v\right)}\right\}\right)}^2\right\}\frac{n^2}{2}\underset{,{}^{}}{\max }{.Math.Q\left(.Math.|,\right)-Q\left(.Math.|{}^{},\right).Math.}_{\mathrm{TV}}{\underset{x,x^1}{\max }\left({}_{}\log \left\{\underset{u,v}{\max }\frac{Q\left(x^{}|u,v\right)}{Q\left(x|u,v\right)}\right\}\right)}^2=n^2{s}_1$