A new technique for compression of data sets

The motivations of the proposed are as follows.

First, we need some notation as follows. Let $X=(\Omega,\Sigma,\mu)$ be a probability space, where $\Omega=\{\omega\}$ is the set of outcomes, $\Sigma$ a $\sigma$–field of measurable subsets in $\Omega$ and $\mu:\Sigma\rightarrow[0,1]$ an associated probability measure on $\Sigma$.

Let $\mbox{$\mathbf{x}$}\in L^{2}(\Omega,{\mathbb{R}}^{n})$ and $\mbox{$\mathbf{y}$}\in L^{2}(\Omega,{\mathbb{R}}^{m})$ be a reference signal and an observed signal, respectively. Let the norm $\|\cdot\|^{2}_{\Omega}$ be given by $\displaystyle\|\mbox{$\mathbf{x}$}\|^{2}_{\Omega}={\int}_{\Omega}\|\mbox{$\mathbf{x}$}(\omega)\|^{2}_{2},d\mu(\omega)$ where $\|\mbox{$\mathbf{x}$}(\omega)\|_{2}$ is the Euclidean norm of $\mbox{$\mathbf{x}$}(\omega)\in{\mathbb{R}}^{m}$.

We consider a linear operator (transform) $\mbox{$\cal K$}:$ $L^{2}(\Omega,{\mathbb{R}}^{m})$ $\rightarrow L^{2}(\Omega,{\mathbb{R}}^{n})$ defined by a matrix $K\in\mbox{$\mathbb{R}$}^{m\times n}$ so that

A generic KLT [7] is the linear transform $\cal K$ that solves

where $\mathbb{K}$ is a class of all linear operators defined by (1). As a result, the KLT returns two matrices, $D\in\mbox{$\mathbb{R}$}^{m\times r}$ and $C\in\mbox{$\mathbb{R}$}^{r\times n}$, so that $K=DC$. Matrix $C$ performs filtering and compression of observed data $\mathbf{y}$ to a shorter vector $\widetilde{\mbox{$\mathbf{x}$}}\in L^{2}(\Omega,{\mathbb{R}}^{r})$ with $r$ components. Matrix $D$ reconstructs $\widetilde{\mbox{$\mathbf{x}$}}$ in such a way that the reconstructed signal is close to $\mathbf{x}$ in the sense of (2).

Operator $\cal K$ that solves (2) for a particular case with $\mbox{$\mathbf{y}$}=\mbox{$\mathbf{x}$}$ is the standard KLT.

Thus, for a given compression ratio, the KLT minimizes the associated error over the class of all linear transforms of the rank defined by (2).

Despite the known KLT optimality, it may happen that the accuracy and compression ratio associated with the KLT are still not satisfactory. Owing to this observation and the KLT versatility in applications (see Section 1 above), the KLT idea was extended in different directions as has been done, in particular, in [2]–[6]. More recent developments in this area include the polynomial transforms [7], extensions of the KLT to the cases of infinite signal sets [9], the best weighted estimators [10, 11], distributed KLT [29] and the fast KLT using wavelets [36].

Nevertheless, the known transforms based on the KLT idea still imply intrinsic difficulties associated with the original KLT. In particular, most of them have been developed for the case of a single signal, and for the fixed compression ratio, the associated error cannot be improved. In the case of the polynomial transforms [7], the error can be improved if the number of terms in the polynomial transforms increase. The latter implies a substantial computational burden that, in many cases, may stifle this intention.

To describe the contribution and compare the features of the proposed transform with those of the KLT-like techniques, we consider the same issues as in Section 1.1.

In this paper, the underlying idea is different from those considered in the above mentioned works. The proposed transform is constructed from a combination of the device of the piece-wise linear function interpolation [1] and the best rank-constrained operator approximation. This means the following.

Suppose, $K_{{}_{Y}}$ and $K_{{}_{X}}$ are uncountable sets of random signals. While the rigorous notation is given in Section 2.2, here, we denote $\mbox{$\mathbf{y}$}(t,\cdot)\in K_{{}_{Y}}$ and $\mbox{$\mathbf{x}$}(t,\cdot)\in K_{{}_{X}}$ where $t\in[a\hskip 5.69054ptb]\subset\mbox{$\mathbb{R}$}$ is a time snapshot. Let $a=t_{1}\leq\ldots\leq t_{p}=b.$ Choose finite numbers of signals, $\{\mbox{$\mathbf{y}$}(t_{1},\cdot),\ldots,\mbox{$\mathbf{y}$}(t_{p},\cdot)\}\subset K_{{}_{Y}}$ and $\{\mbox{$\mathbf{x}$}(t_{1},\cdot),\ldots,\mbox{$\mathbf{x}$}(t_{p},\cdot)\}\subset K_{{}_{X}}$. The proposed transform $\cal F$ contains $p-1$ terms $\mbox{$\cal F$}_{1},\ldots,\mbox{$\cal F$}_{p-1}$ (see (5)–(6) below) where, for $j=1,\ldots,p-1$, each term $\mbox{$\cal F$}_{j}$ is given as a first order operator polynomial (see (6) below) and is determined from the interpolation conditions

A reason for using the approximate equality in (3) is explained in Section 3.3. In Section 3.1, the second condition in (3) is represented as the best rank-constrained approximation problem (11)–(12). As a result, such a transform has advantages that are similar to the known advantages of the piece-wise function interpolation as has been mentioned in Section 1.4. The procedure of data compression-reconstruction is performed via $p-1$ truncated singular value decompositions (SVD) provided in Section 4.3.

Ideally, in (5)–(7), for $j=1,\ldots,p-1$, we would like to determine each $\mbox{$\cal F$}_{j}$ so that $\mbox{$\mathbf{a}$}_{j}$ satisfies

and $\mbox{$\cal G$}_{j}$ solves

The conditions (8)–(9) are motivated by the device of piece-wise function interpolation and associated advantages [1]. In turn, (8) implies $\mbox{$\mathbf{a}$}_{j}=\mbox{$\mathbf{x}$}(t_{j},\cdot)-\mbox{$\cal G$}_{j}[\mbox{$\mathbf{y}$}(t_{j},\cdot)]$ which being substituted in (9), reduces (9) to

where

and $\theta$ is the zero vector.

Nevertheless, the transform $\cal F$ with such $\mbox{$\mathbf{a}$}_{j}$ and $\mbox{$\cal G$}_{j}$ does not provide data compression. To provide compression, we require that instead of (10), $\mbox{$\cal G$}_{j}$ solves

subject to

In (11), we use the notation

The constraint (12) leads to compression of $\mbox{$\mathbf{y}$}(t,\cdot)$ to a shorter vector with $r_{j}$ components. This issue is discussed in more detail in Section 4.3 below.

Thus, a determination of $\cal F$ presented by (5)–(7) is reduced to the following problem: Given $\{\mbox{$\mathbf{x}$}(t_{j},\cdot),\mbox{$\mathbf{y}$}(t_{j},\cdot)\}_{j=1}^{p-1}$, let for $j=1,\ldots,p-1$,

as in (8). Find $\mbox{$\cal G$}_{j}$ that solves (11) subject to (12).

The above term “given” means that covariance matrices associated with $\mbox{$\mathbf{x}$}(t_{j},\cdot)$ are $\mbox{$\mathbf{y}$}(t_{j},\cdot)$ are known or can be estimated. This assumption is similar to the assumption used in the known KLT-like transforms.

We note that (8) and (14) can be represented as

Also, in (11), the term $\mbox{\tiny$\Delta$}\mbox{$\mathbf{x}$}(t_{j},t_{j+1},\cdot)-\mbox{$\cal G$}_{j}[\mbox{\tiny$\Delta$}\mbox{$\mathbf{y}$}(t_{j},t_{j+1},\cdot)]$ can be rewriten as

Therefore, (11)–(12) can be represented as

In other words, the relations (8), (14) and (11)–(12) mean that we wish to determine $\mbox{$\cal F$}_{j}$ so that $\mbox{$\cal F$}_{j}$ exactly interpolates $\mbox{$\mathbf{x}$}(t,\cdot)$ at $t=t_{j}$ and approximately interpolates $\mbox{$\mathbf{x}$}(t,\cdot)$ at $t=t_{j+1}$, as in (15) and (16), respectively.

By this reason, the pairs of signals $\{\mbox{$\mathbf{x}$}(t_{1},\cdot),\mbox{$\mathbf{y}$}(t_{1},\cdot)\},$ $\ldots,\{\mbox{$\mathbf{x}$}(t_{p-1},\cdot),\mbox{$\mathbf{y}$}(t_{p-1},\cdot)\}$ are called the interpolation pairs.

It is worthwhile to note that for the case of pure filtering (with no compression) the constraint (12) is omitted.

First we recall a recent result on the best rank constrained matrix approximation [11, 38] which will be used in the next section.

Let $\mathbb{C}^{m\times n}$ be a set of $m\times n$ complex valued matrices, and denote by $\mathcal{R}(m,n,k)\subseteq\mathbb{C}^{m\times n}$ the variety of all $m\times n$ matrices of rank $k$ at most. Fix $A=[a_{ij}]_{i,j=1}^{m,n}\in\mathbb{C}^{m\times n}$. Then $A^{*}\in\mathbb{C}^{n\times m}$ is the conjugate transpose of $A$. Let the SVD of $A$ be given by

where $U_{A}\in\mathbb{C}^{m\times m}$ and $V_{A}\in\mathbb{C}^{n\times n}\quad\mbox{are unitary matrices,}$ $\Sigma_{A}:=\mbox{diag}(\sigma_{1}(A),\ldots,\sigma_{\min(m,n)}(A))$ $\in\mathbb{C}^{m\times n}$ is a generalized diagonal matrix, with the singular values $\sigma_{1}(A)\geq\sigma_{2}(A)\geq\ldots\geq 0$ on the main diagonal.

Let $U_{A}=[u_{1}\;u_{2}\;\ldots u_{m}]$ and $V_{A}=[v_{1}\;v_{2}\;\ldots v_{n}]$ be the representations of $U$ and $V$ in terms of their $m$ and $n$ columns, respectively. Let

be the orthogonal projections on the range of $A$ and $A^{*}$, correspondingly. Define

for $k=1,\ldots,\mathrm{rank\;}A$, where

For $k>\mathrm{rank\;}A,$ we write $A_{k}:=A\;(=A_{\mathrm{rank\;}A})$. For $1\leq k<\mathrm{rank\;}A$, the matrix $A_{k}$ is uniquely defined if and only if $\sigma_{k}(A)>\sigma_{k+1}(A)$.

Recall that $A^{\dagger}:=V_{A}\Sigma_{A}^{\dagger}U_{A}^{*}\in\mathbb{C}^{n\times m}$ is the Moore-Penrose generalized inverse of $A$, where $\displaystyle\Sigma_{A}^{\dagger}:=\mathrm{diag}\left(\frac{1}{\sigma_{1}(A)},\ldots,\frac{1}{\sigma_{\mathrm{rank\;}A}(A)},0,\ldots,0\right)\in\mathbb{C}^{n\times m}$. See for example [37].

Henceforth $\|\cdot\|$ designates the Frobenius norm.

Theorem 1 below provides a solution to the problem of finding a matrix $X_{0}$ such that

and is based on the fundamental result in [38] (Theorem 2.1) which is a generalization of the well known Eckart-Young theorem [35]. The Eckart-Young theorem states that for the case when $m=p$, $q=n$ and $B=I_{m},$ $C=I_{n}$, the solution is given by $X_{0}=A_{k}$, i.e.

Let us introduce the inner product

and the covariance matrix

We denote by $X^{1/2}$ a matrix such that $X^{1/2}X^{1/2}=X$.

For each $t\in T$, we wish to filter the observed data $\mbox{$\mathbf{y}$}(t,\cdot)\in L^{2}(\Omega,{\mathbb{R}}^{n})$, compress it to a shorter vector $\widetilde{\mbox{$\mathbf{x}$}}(t,\cdot)\in L^{2}(\Omega,{\mathbb{R}}^{r_{j}})$ with $r_{j}=\min\{m,n\}$ components⁷⁷7Recall that in statistics those components are called the principal components [13]. and then to reconstruct $\widetilde{\mbox{$\mathbf{x}$}}(t,\cdot)$ in the form $\widehat{\mbox{$\mathbf{x}$}}(t,\cdot)$ so that $\widehat{\mbox{$\mathbf{x}$}}(t,\cdot)$ is close to $\mbox{$\mathbf{x}$}(t,\cdot)$.

This procedure is provided by the proposed transform $F$ for two special cases,

(i) $t\in(t_{1},\hskip 2.84526ptb]$, and

(ii) $t=t_{1}$

(i) For $t\in(t_{1},\hskip 2.84526ptb]$, compression and filtering of $\mbox{$\mathbf{y}$}(t,\cdot)$ is performed via a representation of $G_{j}$ in (2) as a product of two matrices,

where $D_{G_{j}}$ is a $m\times r_{j}$ matrix and $C_{G_{j}}$ is a $r_{j}\times n$ matrix. Then matrix $C_{G_{j}}$ compresses $\mbox{$\mathbf{x}$}(t_{j},\omega)$ to a vector with $r_{j}$ components and matrix $D_{G_{j}}$ reconstructs the compressed vector so that the reconstruction is close to $\mbox{$\mathbf{x}$}(t_{j},\omega)$.

Matrices $D$ and $C_{j}$ are determined as follows.

Let us write the SVD of $G_{j}$ in (2) as

where matrices

are similar to matrices $U_{A}$, $\Sigma_{A}$ and $V_{A}$ for the SVD of matrix $A$ in (17), respectively. In particular, $\sigma_{j1}$, $\ldots,$ $\sigma_{j\min(m,n)}$ are the associated singular values.

Let us denote