Volume 2013, Issue 1 528281

Research Article

Open Access

On the Low-Rank Approximation Arising in the Generalized Karhunen-Loeve Transform

Xue-Feng Duan

College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Qing-Wen Wang,

Corresponding Author

Qing-Wen Wang

[email protected]

orcid.org/0000-0002-0494-4928

Department of Mathematics, Shanghai University, Shanghai 200444, China shu.edu.cn

Search for more papers by this author

Jiao-Fen Li,

Jiao-Fen Li

College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Xue-Feng Duan,

Xue-Feng Duan

College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Qing-Wen Wang,

Corresponding Author

Qing-Wen Wang

[email protected]

orcid.org/0000-0002-0494-4928

Department of Mathematics, Shanghai University, Shanghai 200444, China shu.edu.cn

Search for more papers by this author

Jiao-Fen Li,

Jiao-Fen Li

College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

First published: 19 May 2013

https://doi.org/10.1155/2013/528281

Citations: 3

Academic Editor: Masoud Hajarian

Share a link

Email
Wechat
Bluesky

Abstract

We consider the low-rank approximation problem arising in the generalized Karhunen-Loeve transform. A sufficient condition for the existence of a solution is derived, and the analytical expression of the solution is given. A numerical algorithm is proposed to compute the solution. The new algorithm is illustrated by numerical experiments.

1. Introduction

Throughout this paper, we use R^m×n to denote the set of m × n real matrices. We use A^T and A⁺ to denote the transpose and Moore-Penrose generalized inverse of the matrix A, respectively. The symbol O^n×n stands for the set of all n × n orthogonal matrices. The symbols rank (A) and ∥A∥_F stand for the rank and the Frobenius norm of the matrix A, respectively. For a = (a_i) ∈ Rⁿ, the symbol ∥a∥ stands for the l₂-norm of the vector a, that is, . The symbol A^1/2 stands for the square root of the matrix A, that is, (A^1/2) ² = A. For the random vector x = (x_i) ∈ Rⁿ, we use E{x_i} to stand for the expected value of the ith entry x_i, and we use E{xx^T} = (e_ij) _n×n to stand for the covariance matrix of the random vector x, where e_ij = E[(x_i − E{x_i})(x_j − E{x_j})], i, j = 1,2, …, n.

The generalized Karhunen-Loeve transform is a well-known signal processing technique for data compression and filtering (see [1–4] for more details). A simple description of the generalized Karhunen-Loeve transform is as follows. Given two random vectors x ∈ Rⁿ, s ∈ R^m and an integer d (1 ≤ d < min {m, n}), the generalized Karhunen-Loeve transform is presented by a matrix T^*, which is a solution of the following minimization problem (see [1, 4]):

()

Here the vector s depends on some prior knowledge about the data x.

Without the rank constraint on T, the solution of the minimization problem (1) is

()

where R_sx = E{sx^T}, R_x = E{xx^T}. The minimization problem with this case is associated with the well-known concept of Wiener filtering (see [3]).

With the rank constraint on T, that is, rank (T) = d, we first consider the cost function of the minimization problem (1). By using the fact

and the four Moore-Penrose equations of

, it is easy to verify that (see also [1])

()

Noting that the covariance matrix R_x is symmetric nonnegative definite, then it can be factorized as

()

Substituting (4) into (3) gives rise to

()

since E{∥s − T₀x∥²} is a constant, then

()

that is to say, minimizing E{∥s−Tx∥²} is equivalent to minimizing

. Therefore, we can find the solution T^* of (1) by solving the minimization problem

()

which can be summarized as the following low rank approximation problem:

Problem 1. Given two matrices A ∈ R^m×n, B ∈ R^p×n and an integer d, 1 ≤ d < m, p, find a matrix of rank d such that

()

In the last few years there has been a constantly increasing interest in developing the theory and numerical approaches for the low rank approximations of a matrix, due to their wide applications. A well-known method for the low rank approximation is the singular value decomposition (SVD) [5, 6]. When the desired rank is relatively low and the matrix is large and sparse, a complete SVD becomes too expensive. Some less expensive alternatives for numerical computation, for example, Lanczos bidiagonalization process [7], and the Monte Carlo algorithm [8] are available. To speed up the computation of SVD, random sampling has been employed in [9]. Recently, Ye [10] proposed the generalized low rank approximations of matrices (GLRAM) method. This method is proved to have less computational time than the traditional singular value decomposition-based methods in practical applications. Later, GLRAM method has been revisited and extended by Liu et al. [11] and Liang and Shi [12]. In some applications, we need to emphasize important parts and deemphasize unimportant parts of the data matrix, so the weighted low rank approximations were considered by many authors. Some numerical methods, such as Newton-like algorithm [13], left versus right representations method [14], and unconstrained optimization method [15], are proposed. Recently, by using the hierarchical identification principle [16] which regards the known matrix as the system parameter matrix to be identified, Ding et al. and Xie et al. present the gradient-based iterative algorithms [16–21] and least-squares-based iterative algorithm [22, 23] for solving matrix equations. The methods are innovational and computationally efficient numerical algorithms.

The common and practical method to tackle the low rank approximation Problem 1 is the singular value decomposition (SVD) (e.g. [1]). We briefly review SVD method as following. Minimizing (8) by a rank-d matrix XB is known [5, Page 69] to satisfy

()

where A_d denotes rank-d singular value decomposition truncation, that is, if the following SVD holds

()

then

. If the matrix B is square and nonsingular, then by (9) we obtain that the solution of Problem 1 is

()

The SVD method has two disadvantages as following: (1) it requires the matrix B to be square and nonsingular; (2) in order to derive the solution (11), we must compute the inverse matrix of B, whose computation cost is very expensive.

In this paper, we develop a new method to solve the low rank approximation Problem 1, which can avoid the disadvantages of SVD method. We first transform Problem 1 into the fixed rank solution of a matrix equation and then use the generalized singular value decomposition (GSVD) to solve it. Based on these, we derive a sufficient condition for the existence of a solution of Problem 1, and the analytical expression of the solution is given. A numerical algorithm is proposed to compute the solution. Numerical examples are used to illustrate the numerical algorithm. The first one is artificial to show that the new algorithm is feasible to solve Problem 1, and the second is simulation, which shows that the new algorithm can be used to realize the image compression.

2. Main Results

In this section, we give a sufficient condition and an analytical expression for the solution of Problem 1 by transforming Problem 1 into the fixed rank solution of a matrix equation. Finally, we establish an algorithm for solving Problem 1.

Lemma 2. A matrix is a solution of Problem 1 if and only if it is a solution of the following matrix equation:

()

Proof. It is easy to verify that a matrix is a solution of Problem 1 if and only if satisfies the following two equalities simultaneously:

()

Since the normal equation of the least squares problem (13) is

()

and noting that the least squares problem (13) and its normal equation (15) have the same solution sets, then (13) and (14) can be equivalently written as

()

which also imply that Problem 1 is equivalent to (12).

Remark 3. From Lemma 2 it follows that Problem 1 is equivalent to (12), hence we can solve Problem 1 by finding a fixed rank solution of the matrix equation XBB^T = AB^T.

Now we will use generalized singular value decomposition (GSVD) to solve (12). Set

()

The GSVD of the matrix pair (C, D) is given by (see [24])

()

where U ∈ O^p×p, V ∈ O^m×m, W ∈ R^p×p is a nonsingular matrix, k = rank ([C^T, D^T]), r = rank (C), t = rank (C) + rank (D) − rank ([C^T, D^T]), and

()

are block matrices, with I_C and I_D are identity matrices, O_C and O_D are zero matrices:

()

By (17) and (18), we have

()

Set

()

and Y is partitioned as follows:

()

then

()

Therefore, by (21) and (24), we have

()

that is to say, the matrix equation XBB^T = AB^T has a solution if and only if

()

and according to (22), we know that the expression of the solution is

()

where

()

By (26)–(28) and noting that Y₁₃ and Y₂₃ are arbitrary matrices, we have

()

Hence, if

()

then (12) has a solution, and the expressions of the solution are given by (26)–(28), that is,

()

where Y₂₃ ∈ R^t×(p−r) is an arbitrary matrix and Y₁₃ ∈ R^{(m−t)×(p−r)} is chosen such that

()

And noting that the low rank approximation Problem 1 is equivalent to (12) (i.e. Lemma 2), then we obtain the following.

Theorem 4. If

()

then Problem 1 has a solution, and the expressions of the solution are given by

()

where Y₂₃ ∈ R^t×(p−r) is an arbitrary matrix and Y₁₃ ∈ R^{(m−t)×(p−r)} is chosen such that

()

Remark 5. In contrast with (11), the solution expression (35) does not require the matrix B to be square and nonsingular and does not need to compute the inverse of B.

Based on Theorem 4, we can establish an algorithm for finding the solution of Problem 1.

Algorithm 6. (1) Input the matrices A, B and the integer d;

(2)
make the GSVD of the matrix pair (C, D) according to (18);
(3)
choose Y₂₃ ∈ R^t×(p−r) and Y₁₃ ∈ R^{(m−t)×(p−r)}, such that rank (Y₁₃) = d − rank (AB^T);
(4)
compute the solution X according to (35).

3. Numerical Experiments

In this section, we first use a simple artificial example to illustrate that Algorithm 6 is feasible to solve Problem 1, then we use a simulation to show that Algorithm 6 can be used to realize the image compression. The experiments were done with MATLAB 7.6 on a 64-bit Intel Pentium Xeon 2.66 GHz with e_mach ≈ 2.0 × 10⁻¹⁶.

Example 7. Consider Problem 1 with

()

We make GSVD of the matrix pair (C, D) = (BB^T, AB^T) as follows:

()

where

()

It is easy to verify that

()

that is, if 2 ≤ d ≤ 5, then the conditions of Theorem 4 are satisfied. Setting d = 2 ∈ [2,5], according to (35), we obtain that the solution of Problem 1 is

()

Setting d = 4 ∈ [2,5], according to (35), we obtain that the solution of Problem 1 is

()

Example 7 shows that Algorithm 6 is feasible to solve Problem 1. However, the SVD method in [1] cannot be used to solve Example 7, because B is not a square matrix.

Example 8. We will use the generalized Karhunen-Loeve transform, based on Algorithm 6 and SVD method in [1], respectively, to realize the image compression. Figure 1(a) (see page 3) is the test image which has 256 × 256 pixels and 256 levels on each pixel. We separate it into 32 × 32 blocks such that each block has 8 × 8 pixels. Let and (i, j = 0,1, 2, …, 7; k, l = 0,1, 2, …, 31) be the values of the image and a Gaussian noise (generated by Matlab function imnoise) at the (i, j)th pixel in the (k, l)th block, respectively. For convenience, let a = i + 8j, p = k + 32l, and the (i, j)th pixel in the (k, l)th block be expressed as the ath pixel in the pth block (a = 0,1, 2, …, 63; p = 0,1, …, 1023). We can also express and as and , respectively.

The test image is processed on each block. Therefore, we can assume that the blocked image space is 64-D real vector space R⁶⁴. The pth block of the original image is expressed by the pth vector:

()

Hence the original image is expressed by 1024 64-D vectors

. The noise is similarly expressed by

, where

()

Figure 1(b) is the noisy image

, where

()

By (47), (49), (2), (4) and the definition of covariance matrix, we get T₀ and

of (7). Then we use Algorithm 6 and SVD method in [1] to realize the image compression respectively, and the experiment results are in pages 4 and 5.

Figure 2 illustrates that Algorithm 6 can be used to realize image compression. Although it is difficult to see the difference between Figures 2 and 3, which are compressed by SVD method in [1], from Table 1 we can see that the execution time of Algorithm 6 is less than that of SVD method at the same rank. This shows that our algorithm outperforms the SVD method in execution time.

Table 1. Execution time for deriving Figures 2(a)–3(c).

Figure 2(a)	Figure 3(a)	Figure 2(b)	Figure 3(b)	Figure 2(c)	Figure 3(c)
3.5835 (s)	3.9216 (s)	2.8627 (s)	3.0721 (s)	2.0591 (s)	2.1433 (s)

Details are in the caption following the image — **Figure 1 (a)**
Open in figure viewer PowerPoint

(a) Original image; (b) noisy image.

4. Conclusion

The low rank approximation Problem 1 arising in the generalized Karhunen-Loeve transform is studied in this paper. We first transform Problem 1 into the fixed rank solution of a matrix equation and then use the generalized singular value decomposition (GSVD) to solve it. Based on these, we derive a sufficient condition for the existence of a solution, and the analytical expression of the solution is also given. Finally, we use numerical experiments to show that new algorithm is feasible and effective.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (11101100; 11226323; 11261014; and 11171205), the Natural Science Foundation of Guangxi Province (2012GXNSFBA053006; 2013GXNSFBA019009; and 2011GXNSFA018138), the Key Project of Scientific Research Innovation Foundation of Shanghai Municipal Education Commission (13ZZ080), the Natural Science Foundation of Shanghai (11ZR1412500), the Ph.D. Programs Foundation of Ministry of Education of China (20093108110001), the Discipline Project at the corresponding level of Shanghai (A. 13-0101-12-005), and Shanghai Leading Academic Discipline Project (J50101).

References

1 Hua Y. and Liu W. Q., Generalized Karhunen-Loeve transform, IEEE Signal Processing Letters. (1998) 5, 141–142.
10.1109/97.681430
Web of Science® Google Scholar
2 Kraut S., Anderson R. H., and Krolik J. L., A generalized Karhunen-Loeve basis for efficient estimation of tropospheric refractivity using radar clutter, IEEE Transactions on Signal Processing. (2004) 52, no. 1, 48–60, https://doi.org/10.1109/TSP.2003.820297, MR2049873.
10.1109/TSP.2003.820297
Web of Science® Google Scholar
3 Ogawa H. and Oja E., Projection filter, Wiener filter, and Karhunen-Loève subspaces in digital image restoration, Journal of Mathematical Analysis and Applications. (1986) 114, no. 1, 37–51, https://doi.org/10.1016/0022-247X(86)90063-6, MR829109, ZBL0588.94005.
10.1016/0022-247X(86)90063-6
Web of Science® Google Scholar
4 Yamashita Y. and Ogawa H., Relative Karhumen-Loeve transform, IEEE Transactions on Signal Process. (1996) 44, 371–378.
10.1109/78.485932
Web of Science® Google Scholar
5 Golub G. H. and Van Loan C. F., Matrix Computations, 1996, 3rd edition, Johns Hopkins University Press, Baltimore, Md, USA, MR1417720.
CAS Web of Science® Google Scholar
6 Hansen P. C., The truncated SVD as a method for regularization, BIT Numerical Mathematics. (1987) 27, no. 4, 534–553, https://doi.org/10.1007/BF01937276, MR916729, ZBL0633.65041.
10.1007/BF01937276
Web of Science® Google Scholar
7 Simon H. D. and Zha H., Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM Journal on Scientific Computing. (2000) 21, no. 6, 2257–2274, https://doi.org/10.1137/S1064827597327309, MR1762041, ZBL0962.65038.
10.1137/S1064827597327309
Web of Science® Google Scholar
8 Drineas P., Kannan R., and Mahoney M. W., Fast Monte Carlo algorithms for matrices—II. Computing a low-rank approximation to a matrix, SIAM Journal on Computing. (2006) 36, no. 1, 158–183, https://doi.org/10.1137/S0097539704442696, MR2231644, ZBL1111.68148.
10.1137/S0097539704442696
Web of Science® Google Scholar
9 Frieze A., Kannan R., and Vempala S., Fast Monte-Carlo algorithms for finding low-rank approximations, Journal of the ACM. (2004) 51, no. 6, 1025–1041, https://doi.org/10.1145/1039488.1039494, MR2145262, ZBL1125.65005.
10.1145/1039488.1039494
Web of Science® Google Scholar
10 Ye J. P., Generalized low rank approximations of matrices, Machine Learning. (2005) 61, 167–191.
10.1007/s10994-005-3561-6
Web of Science® Google Scholar
11 Liu J., Chen S. C., Zhou Z. H., and Tan X. Y., Generalized low rank approximations of matrices revisited, IEEE Transactions on Neural Networks. (2010) 21, 621–632.
10.1109/TNN.2010.2040290
PubMed Google Scholar
12 Liang Z. Z. and Shi P. F., An analytical algorithm for generalized low rank approxiamtions of matrices, Pattern Recognition. (2005) 38, 2213–2216.
10.1016/j.patcog.2005.04.012
Web of Science® Google Scholar
13 Manton J. H., Mahony R., and Hua Y., The geometry of weighted low-rank approximations, IEEE Transactions on Signal Processing. (2003) 51, no. 2, 500–514, https://doi.org/10.1109/TSP.2002.807002, MR1956702.
10.1109/TSP.2002.807002
Web of Science® Google Scholar
14 Markovsky I. and Van Huffel S., Left versus right representations for solving weighted low-rank approximation problems, Linear Algebra and its Applications. (2007) 422, no. 2-3, 540–552, https://doi.org/10.1016/j.laa.2006.11.012, MR2305139, ZBL1115.65047.
10.1016/j.laa.2006.11.012
Web of Science® Google Scholar
15 Schuermans M., Lemmerling P., and Van Huffel S., Block-row Hankel weighted low rank approximation, Numerical Linear Algebra with Applications. (2006) 13, no. 4, 293–302, https://doi.org/10.1002/nla.459, MR2220675, ZBL1174.65390.
10.1002/nla.459
Web of Science® Google Scholar
16 Ding F. and Chen T., On iterative solutions of general coupled matrix equations, SIAM Journal on Control and Optimization. (2006) 44, no. 6, 2269–2284, https://doi.org/10.1137/S0363012904441350, MR2248183, ZBL1115.65035.
10.1137/S0363012904441350
Web of Science® Google Scholar
17 Ding F. and Chen T., Gradient based iterative algorithms for solving a class of matrix equations, IEEE Transactions on Automatic Control. (2005) 50, no. 8, 1216–1221, https://doi.org/10.1109/TAC.2005.852558, MR2156053.
10.1109/TAC.2005.852558
Web of Science® Google Scholar
18 Ding F., Liu P. X., and Ding J., Iterative solutions of the generalized Sylvester matrix equations by using the hierarchical identification principle, Applied Mathematics and Computation. (2008) 197, no. 1, 41–50, https://doi.org/10.1016/j.amc.2007.07.040, MR2396289, ZBL1143.65035.
10.1016/j.amc.2007.07.040
Web of Science® Google Scholar
19 Ding J., Liu Y., and Ding F., Iterative solutions to matrix equations of the form AiXBi = Fi, Computers & Mathematics with Applications. (2010) 59, no. 11, 3500–3507, https://doi.org/10.1016/j.camwa.2010.03.041, MR2646321, ZBL1197.15009.
10.1016/j.camwa.2010.03.041
Web of Science® Google Scholar
20 Xie L., Liu Y., and Yang H., Gradient based and least squares based iterative algorithms for matrix equations AXB + CX^TD = F, Applied Mathematics and Computation. (2010) 217, no. 5, 2191–2199, https://doi.org/10.1016/j.amc.2010.07.019, MR2727965, ZBL1210.65097.
10.1016/j.amc.2010.07.019
Web of Science® Google Scholar
21 Xie L., Ding J., and Ding F., Gradient based iterative solutions for general linear matrix equations, Computers & Mathematics with Applications. (2009) 58, no. 7, 1441–1448, https://doi.org/10.1016/j.camwa.2009.06.047, MR2555281, ZBL1189.65083.
10.1016/j.camwa.2009.06.047
Web of Science® Google Scholar
22 Ding F. and Chen T., Iterative least-squares solutions of coupled Sylvester matrix equations, Systems & Control Letters. (2005) 54, no. 2, 95–107, https://doi.org/10.1016/j.sysconle.2004.06.008, MR2109576, ZBL1129.65306.
10.1016/j.sysconle.2004.06.008
Web of Science® Google Scholar
23 Xiong W., Fan W., and Ding R., Least-squares parameter estimation algorithm for a class of input nonlinear systems, Journal of Applied Mathematics. (2012) 2012, 14, https://doi.org/10.1155/2012/684074, 684074, MR2959986, ZBL1251.62036.
10.1155/2012/684074
Google Scholar
24 Paige C. C. and Saunders M. A., Towards a generalized singular value decomposition, SIAM Journal on Numerical Analysis. (1981) 18, no. 3, 398–405, https://doi.org/10.1137/0718026, MR615522, ZBL0471.65018.
10.1137/0718026
Web of Science® Google Scholar

Citing Literature

All articles

On the Low-Rank Approximation Arising in the Generalized Karhunen-Loeve Transform

Abstract

1. Introduction

2. Main Results

3. Numerical Experiments

4. Conclusion

Acknowledgments

References

Citing Literature

Figures

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

On the Low-Rank Approximation Arising in the Generalized Karhunen-Loeve Transform

Abstract

1. Introduction

2. Main Results

3. Numerical Experiments

4. Conclusion

Acknowledgments

References

Citing Literature

Figures

References

Related

Information