# Data Recovery Technology Based on Subspace Clustering

Authors: Li Sun; Bing Song
Journal: Scientific Programming
 (2022)

---

## Abstract

High-dimensional data usually exist asymptotically in low-dimensional space. In this study, we mainly use tensor t-product as a tool to propose new algorithms in data clustering and recovery and verify them on classical data sets. This study defines the “singular values” of tensors, adopts a weighting strategy for the singular values, and proposes a tensor-weighted kernel norm minimization robust principal component analysis method, which is used to restore low-probability low-rank third-order tensor data. Experiments on synthetic data show that in the recovery of strictly low-rank data, the tensor method and weighting strategy can also obtain more accurate recovery when the rank is relatively large, which improves the volume of the rank. The proposed method combines the two and reflects its superiority through the restoration of 500 images under a small probability noise level.


---

## Body

## 1. Introduction

In recent years, the development of science and technology has been changing with each passing day, and at the same time, it has also brought complicated data [1–4]. With the development of the Internet and artificial intelligence [5–8], the data on education, medical treatment, e-commerce, transportation, and other industries show explosive growth. How to mine useful information from massive data has become a research hotspot. Due to the continuous improvement of people’s ability to obtain data, the scale of data is becoming larger and larger, and the structure is becoming more and more complex, such as millions of frames of video, texts, and web pages carrying hundreds of millions of information.Data recovery and clustering are of great significance to the analysis of high-dimensional data [9–14]. Many high-dimensional data usually exist approximately in low-dimensional subspaces, and the low rank prior of data becomes the key to effective data recovery [15–18]. In cluster analysis, many data are usually modeled as coming from multiple cluster subspaces. Based on this, the data are clustered and a popular subspace clustering algorithm is formed.Analyzing these high-dimensional data not only occupies memory and takes time but also because the useful information of the data often only exists in the low-dimensional space, other redundant components will bring great interference to the analysis algorithm [19]. Noise or outliers due to the increase of information will also affect the performance of the algorithm. How to grasp and make use of the characteristics of data has become a breakthrough in the effective analysis of data. In the form of data processing, the traditional method of matrix decomposition usually needs to transform multi-level data samples into column vectors, which inevitably destroys the original structure of data and leads to information loss. While retaining the original form of the data, the tensor form will be used for decomposition. In recent years, in the field of practical application, the analysis of tensors has played an increasingly important role, so more and more scholars have paid attention to it. The forms of tensor operations are diversified with the in-depth exploration of the academic community.


## 2. Data Recovery of Low-Rank Third-Order Tensors under Small Probability Sparse Noise

Low rank exists widely in data. In algorithms applied to traditional matrix factorization, converting each multi-order data sample into a long column vector form is necessary [20]. A third-order tensor has a lower-rank structure than the corresponding matrix. Therefore, theoretically, from the perspective of low-rank recovery, the original structure of tensors has certain advantages.Theorem 1.
For any tensor:(1)A∈ℝn1×n2×n3.
We convert each of its side slice matrices into a column vector, the matrixA is formed by these column vectors, which is unfold (A).
Then the average rank ofA is less than or equal to the rank of A, that is,(2)raA≤runfoldA.
Prove:(3)bcircA=In1n3,P,P2,…,Pn3−1AA⋱A,where P is the permutation matrix O⋯OIn1In1⋯OO⋮⋱⋮⋮O⋯In1O∈ℝn1n3×n1n3.
Then,(4)raA=1n3rbdiagA=1n3rbcircA.
So,(5)raA≤1n3rAA⋱A=rA.


### 2.1. Tensor Low-Rank Structure of RGB Images

An RGB image data itself is a third-order tensor, and the general image tensor has a low-rank structure, which will be explained from experiments in this section. Two-color pictures are randomly selected from the Berkeley Segmentation dataset [21], and the picture size is 321 × 481. Each picture’s data (RGB picture) can be regarded as a third-order tensor (set as A∈ℝm×n×3). We perform tensor singular value decomposition for each image: A=U∗S∗V∗. Also, we calculate the singular value of bdiagA. It can be seen that the general RGB image itself has a tensor low-rank structure.Tensor low-rank representation (TLRR) [22] and tensor robust principal component analysis (TRPCA) [23] use the tensor low-rank structure to remove the sparse noise of the image. The decomposition of TRPCA is shown in Figure 1.Figure 1
Schematic diagram of TRPCA decomposition.


### 2.2. Tensor-Weighted Nuclear Norm Minimization Robust Principal Component Analysis Method

Perform singular value decomposition on a matrix of approximately low rank; the larger singular value corresponds to the “main structure” information of the matrix, such as larger edges and smooth parts in the image matrix. The small noise does not interfere much with the main structure of the matrix; therefore, in the denoising algorithm based on singular value shrinkage, different singular values should be treated differently. Based on this prior, weighted nuclear norm minimization (WNNM) [24] and weighted nuclear norm minimization-robust principal component analysis (WNNM-RPCA) [25] give a small degree of shrinkage to large singular values based on nuclear norm minimization (NNM) and robust principal component analysis (RPCA), respectively, and greatly improve the denoising effect.The singular value of any tensorA is defined as the singular value of bdiagA; then, the above analysis is also valid for tensor singular value decomposition. Referring to the weighting strategy in literature [26], we set the weight of each singular value σi of the tensor as(6)wit+1=CσiAt+ϵ.In this equation,σi represents the i-th singular value of A, t represents the number of iterations, C is a normal number, and ε is a minimal number to prevent the denominator from being 0.TheL1 norm is often used to characterize random probability noise. For example, RPCA, etc. For the problem of removing small probability noises from third-order tensors, a tensor-weighted nuclear norm minimization robust principal component analysis method is proposed as(7)minℒ,Eℒw,∗+E1,s.t.x=ℒ+ɛ.To deal with the equality constraint problem, the augmented lagrange multiplier method is used, that is,(8)minℒ,Eℒw,∗+λE1+μ2X−ℒ−E2+<y,X−ℒ−E>.We solve equation (8) by the alternating direction method of multipliers (ADMM) method. This is a supplementary explanation of the solution to the following model used to update ℒ.Giving the tensorZ∈ℝn1×n2×n3, the ℒ of the following function is solved as(9)minℒℒw,∗+μ2ℒ−Z2.This is equivalent to the following matrix model:(10)minℒbdiagℒw,∗+μ2bdiagℒ−bdiagZ2.Let(11)bdiagℒ=L1L2⋱Ln3,bdiagZ=Z1Z2⋱Zn3,where Li,Zi∈ℝn1×n2,i=1,…,n3.Then, the model can be transformed into(12)minLiLi,w,∗+μ2Li−Zi2,i=1…,n3.It can be solved by applying Theorem2.Theorem 2 ([see25]).
SupposeY∈ℝm×n, for the wavelet neural network prediction (WNNP) problem of the reweighted strategy:(13)minXXw,∗+Y−X2,where wit=C/σiXt+ϵ, C is a positive constant, ϵ satisfies ϵ<minC,C/σ1Y and initializes X0=Y, then the problem has a closed-form solution.
We perform singular value decomposition onY:(14)Y=U∑V.
Then, the closed-form solution is(15)X∗=U∑VT,where,(16)∑=diagσ1X∗,σ2X∗,…,σnX∗0˜,σiX∗=0c2<0,c1+c22c2≥0,c1=σiY−ϵ,c2=σiY+ϵ2−4C.


## 2.1. Tensor Low-Rank Structure of RGB Images

An RGB image data itself is a third-order tensor, and the general image tensor has a low-rank structure, which will be explained from experiments in this section. Two-color pictures are randomly selected from the Berkeley Segmentation dataset [21], and the picture size is 321 × 481. Each picture’s data (RGB picture) can be regarded as a third-order tensor (set as A∈ℝm×n×3). We perform tensor singular value decomposition for each image: A=U∗S∗V∗. Also, we calculate the singular value of bdiagA. It can be seen that the general RGB image itself has a tensor low-rank structure.Tensor low-rank representation (TLRR) [22] and tensor robust principal component analysis (TRPCA) [23] use the tensor low-rank structure to remove the sparse noise of the image. The decomposition of TRPCA is shown in Figure 1.Figure 1
Schematic diagram of TRPCA decomposition.


## 2.2. Tensor-Weighted Nuclear Norm Minimization Robust Principal Component Analysis Method

Perform singular value decomposition on a matrix of approximately low rank; the larger singular value corresponds to the “main structure” information of the matrix, such as larger edges and smooth parts in the image matrix. The small noise does not interfere much with the main structure of the matrix; therefore, in the denoising algorithm based on singular value shrinkage, different singular values should be treated differently. Based on this prior, weighted nuclear norm minimization (WNNM) [24] and weighted nuclear norm minimization-robust principal component analysis (WNNM-RPCA) [25] give a small degree of shrinkage to large singular values based on nuclear norm minimization (NNM) and robust principal component analysis (RPCA), respectively, and greatly improve the denoising effect.The singular value of any tensorA is defined as the singular value of bdiagA; then, the above analysis is also valid for tensor singular value decomposition. Referring to the weighting strategy in literature [26], we set the weight of each singular value σi of the tensor as(6)wit+1=CσiAt+ϵ.In this equation,σi represents the i-th singular value of A, t represents the number of iterations, C is a normal number, and ε is a minimal number to prevent the denominator from being 0.TheL1 norm is often used to characterize random probability noise. For example, RPCA, etc. For the problem of removing small probability noises from third-order tensors, a tensor-weighted nuclear norm minimization robust principal component analysis method is proposed as(7)minℒ,Eℒw,∗+E1,s.t.x=ℒ+ɛ.To deal with the equality constraint problem, the augmented lagrange multiplier method is used, that is,(8)minℒ,Eℒw,∗+λE1+μ2X−ℒ−E2+<y,X−ℒ−E>.We solve equation (8) by the alternating direction method of multipliers (ADMM) method. This is a supplementary explanation of the solution to the following model used to update ℒ.Giving the tensorZ∈ℝn1×n2×n3, the ℒ of the following function is solved as(9)minℒℒw,∗+μ2ℒ−Z2.This is equivalent to the following matrix model:(10)minℒbdiagℒw,∗+μ2bdiagℒ−bdiagZ2.Let(11)bdiagℒ=L1L2⋱Ln3,bdiagZ=Z1Z2⋱Zn3,where Li,Zi∈ℝn1×n2,i=1,…,n3.Then, the model can be transformed into(12)minLiLi,w,∗+μ2Li−Zi2,i=1…,n3.It can be solved by applying Theorem2.Theorem 2 ([see25]).
SupposeY∈ℝm×n, for the wavelet neural network prediction (WNNP) problem of the reweighted strategy:(13)minXXw,∗+Y−X2,where wit=C/σiXt+ϵ, C is a positive constant, ϵ satisfies ϵ<minC,C/σ1Y and initializes X0=Y, then the problem has a closed-form solution.
We perform singular value decomposition onY:(14)Y=U∑V.
Then, the closed-form solution is(15)X∗=U∑VT,where,(16)∑=diagσ1X∗,σ2X∗,…,σnX∗0˜,σiX∗=0c2<0,c1+c22c2≥0,c1=σiY−ϵ,c2=σiY+ϵ2−4C.


## 3. Experiments

It is assumed that the value range of each element in the low-rank tensorA is [a, b], and the element with frequency p in A is disturbed by noise. This experiment mainly explores the accurate recovery of low-rank third-order tensor A∈ℝn1×n2×n3 under low-probability sparse noise by the proposed tensor-weighted nuclear norm minimization robust principal component analysis method.The main comparison algorithms are RPCA [27], WNNM-RPCA [25], low-rank representation (LRR) [28], tensor robust principal component analysis (TRPCA) [23], and tensor low-rank representation (TLRR) [22]. Each positive slice matrix of the tensor is denoised separately when applying the matrix methods: WNNM-RPCA and LRR.In addition to the parameters already set, set(17)C=4pn1n2.p value prior is needed here. Better results can be obtained without p prior value, but experiments show that setting the C value in this way is more effective.


### 3.1. Synthesis of Data

Firstly, the vector linearly produces a low-rank tensor. The steps of this experiment are:(1)
Generate a low-rank tensor:(18)A=foldunfoldℬC,whereℬ∈ℝn1×r×n3,C∈ℝr×n2, all obey the normal distribution N0,1.(2)
Randomly select the element whose proportion frequency isp from A and set it as a large random value in the range of [a, b]. [a, b] is set as the value range minA,maxA of A.(3)
Use the corresponding algorithm to process separately to get the recovery valueA∗.(4)
Comparing the relative error,(19)RF=A−A∗A.The restoration fails if the error is greater than 0.2.Then, we fixn1  = 300, n2  = 300, n3  = 5, p=0.15 unchanged, set r to 5, 10, 15, 20, 40, 60, 80, respectively. Each group of experiments generates 10 noise data recovered by different algorithms (each row in the error result table uses the same group of data), and the average results are taken. A comparison of recovery errors for low-rank tensors produced by vector linearity is shown in Table 1.Table 1
Comparison of recovery errors for low-rank tensors produced by vector linearity.
rRPCAWNNM-RPCATRPCATWRPCA55.58e − 113.86e − 081.23e − 081.01e − 08105.64e − 114.70e − 081.12e − 081.08e − 08154.88e − 115.65e − 087.76e − 091.04e − 08205.21e − 116.26e − 081.11e − 089.44e − 09405.98e − 111.01e − 073.78e − 049.23e − 09600.134.55e − 040.121.55e − 0980————“—” indicates that recovery failed.Then, tensors linearly generate low-rank tensors. This experiment is different from the first experiment only in the method of generating low-rank tensors in step 1, which is changed to(20)A=B∗C,where ℬ∈ℝn1×r×n3,C∈ℝr×n2×n3, all obey the normal distribution: N0,1. The results are shown in Table 2.Table 2
Comparison of recovery errors for low-rank tensors produced by tensor linearity.
rRPCAWNNM-RPCATRPCATWRPCA55.39e − 117.69e − 088.51e − 096.21e − 09100.0121.31e − 076.84e − 096.72e − 0915——7.22e − 095.78e − 0920——4.24e − 093.92e − 0940——1.04e − 084.70e − 0960——0.126.72e − 0980———9.62e − 09“—” indicates that recovery failed.From the above two experiments, we can draw the following conclusions: in the case of low-rank and low-noise level, the inpainting result of RPCA is the most accurate. This also verifies the theory described in [27]. From the perspective of “tolerance” to rank, both the tensor method and the weighting strategy make the original algorithm significantly improved. The improvement effect of the tensor method is particularly significant in the recovery of data generated by tensor linearity.


### 3.2. Image Restoration

This experiment uses 500 pictures from the Berkeley dataset [27–29] under different scenarios. For each test picture, the pixel value of p = 3%～15% is randomly selected and set to a random value of [0, 255], and different algorithms are applied to repair. When applying the proposed tensor weighted nuclear norm minimization robust principal component analysis method, the experiments show that the denoising results need to be performed twice by the proposed tensor weighted nuclear norm minimization robust principal component analysis method for better results. Taking mean square error (MSE) and peak signal to noise ratio (PSNR) values as evaluation indicators:(21)MSE=ℒ−X2n1n2n3,PSNR=10log10X∞2MSE,where ℒ is the recovery result for X∈ℝn1×n2×n3.Under the noise level ofp = 9%, each algorithm recovers the data of four example images. The average processing time of the four images is shown in Figure 2. MATLABR 2020 is used in this experiment, the computer parameters are the operating system win10, CPU Inter(R) Core(TM) i5-3230M, CPU of 2.60 GHZ, and the memory of 8 GB.Figure 2
Average time to recover four example images whenp = 9% (unit: seconds).Under different noise levels, each algorithm restores 500 images, and the average MSE and PSNR values are shown in Tables3 and 4, respectively (the best results are shown in bold).Table 3
Average MSE value recovered from 500 pictures.
p = 3%p = 6%p = 9%p = 12%p = 15%RPCA199.78214.66226.93242.23260.63LRR174.63186.30196.63215.69241.02WNNM-RPCA72.10115.63171.23220.28266.78TRPCA65.7878.6288.52101.08118.52TLRR42.2548.5255.3265.2977.04The proposed method17.6523.0536.1155.8579.55Table 4
Average PSNR value recovered from 500 pictures.
p = 3%p = 6%p = 9%p = 12%p = 15%RPCA24.5525.7425.4425.7125.00LRR26.2125.9625.6325.6324.25WNNM-RPCA30.6627.8526.5025.2124.30TRPCA30.2530.1029.6628.6127.96TLRR32.6231.5731.6830.5129.82The proposed method38.5536.3232.8031.0229.01It can be seen from Tables3 and 4 that the repair results of the tensor method are better than the repair results of the matrix method; WNNM-RPCA and TWRPCA obtained by the weighted strategy perform better in similar methods, and the lower the noise level, the more pronounced the advantage of the weighted strategy.As mentioned above, the larger part of the singular value of the data represents the “main structure” of the data itself. At the same time, the low noise level has less influence on the main structure of the data, and the weighting strategy uses this prior. The experimental results further verified this hypothesis.


## 3.1. Synthesis of Data

Firstly, the vector linearly produces a low-rank tensor. The steps of this experiment are:(1)
Generate a low-rank tensor:(18)A=foldunfoldℬC,whereℬ∈ℝn1×r×n3,C∈ℝr×n2, all obey the normal distribution N0,1.(2)
Randomly select the element whose proportion frequency isp from A and set it as a large random value in the range of [a, b]. [a, b] is set as the value range minA,maxA of A.(3)
Use the corresponding algorithm to process separately to get the recovery valueA∗.(4)
Comparing the relative error,(19)RF=A−A∗A.The restoration fails if the error is greater than 0.2.Then, we fixn1  = 300, n2  = 300, n3  = 5, p=0.15 unchanged, set r to 5, 10, 15, 20, 40, 60, 80, respectively. Each group of experiments generates 10 noise data recovered by different algorithms (each row in the error result table uses the same group of data), and the average results are taken. A comparison of recovery errors for low-rank tensors produced by vector linearity is shown in Table 1.Table 1
Comparison of recovery errors for low-rank tensors produced by vector linearity.
rRPCAWNNM-RPCATRPCATWRPCA55.58e − 113.86e − 081.23e − 081.01e − 08105.64e − 114.70e − 081.12e − 081.08e − 08154.88e − 115.65e − 087.76e − 091.04e − 08205.21e − 116.26e − 081.11e − 089.44e − 09405.98e − 111.01e − 073.78e − 049.23e − 09600.134.55e − 040.121.55e − 0980————“—” indicates that recovery failed.Then, tensors linearly generate low-rank tensors. This experiment is different from the first experiment only in the method of generating low-rank tensors in step 1, which is changed to(20)A=B∗C,where ℬ∈ℝn1×r×n3,C∈ℝr×n2×n3, all obey the normal distribution: N0,1. The results are shown in Table 2.Table 2
Comparison of recovery errors for low-rank tensors produced by tensor linearity.
rRPCAWNNM-RPCATRPCATWRPCA55.39e − 117.69e − 088.51e − 096.21e − 09100.0121.31e − 076.84e − 096.72e − 0915——7.22e − 095.78e − 0920——4.24e − 093.92e − 0940——1.04e − 084.70e − 0960——0.126.72e − 0980———9.62e − 09“—” indicates that recovery failed.From the above two experiments, we can draw the following conclusions: in the case of low-rank and low-noise level, the inpainting result of RPCA is the most accurate. This also verifies the theory described in [27]. From the perspective of “tolerance” to rank, both the tensor method and the weighting strategy make the original algorithm significantly improved. The improvement effect of the tensor method is particularly significant in the recovery of data generated by tensor linearity.


## 3.2. Image Restoration

This experiment uses 500 pictures from the Berkeley dataset [27–29] under different scenarios. For each test picture, the pixel value of p = 3%～15% is randomly selected and set to a random value of [0, 255], and different algorithms are applied to repair. When applying the proposed tensor weighted nuclear norm minimization robust principal component analysis method, the experiments show that the denoising results need to be performed twice by the proposed tensor weighted nuclear norm minimization robust principal component analysis method for better results. Taking mean square error (MSE) and peak signal to noise ratio (PSNR) values as evaluation indicators:(21)MSE=ℒ−X2n1n2n3,PSNR=10log10X∞2MSE,where ℒ is the recovery result for X∈ℝn1×n2×n3.Under the noise level ofp = 9%, each algorithm recovers the data of four example images. The average processing time of the four images is shown in Figure 2. MATLABR 2020 is used in this experiment, the computer parameters are the operating system win10, CPU Inter(R) Core(TM) i5-3230M, CPU of 2.60 GHZ, and the memory of 8 GB.Figure 2
Average time to recover four example images whenp = 9% (unit: seconds).Under different noise levels, each algorithm restores 500 images, and the average MSE and PSNR values are shown in Tables3 and 4, respectively (the best results are shown in bold).Table 3
Average MSE value recovered from 500 pictures.
p = 3%p = 6%p = 9%p = 12%p = 15%RPCA199.78214.66226.93242.23260.63LRR174.63186.30196.63215.69241.02WNNM-RPCA72.10115.63171.23220.28266.78TRPCA65.7878.6288.52101.08118.52TLRR42.2548.5255.3265.2977.04The proposed method17.6523.0536.1155.8579.55Table 4
Average PSNR value recovered from 500 pictures.
p = 3%p = 6%p = 9%p = 12%p = 15%RPCA24.5525.7425.4425.7125.00LRR26.2125.9625.6325.6324.25WNNM-RPCA30.6627.8526.5025.2124.30TRPCA30.2530.1029.6628.6127.96TLRR32.6231.5731.6830.5129.82The proposed method38.5536.3232.8031.0229.01It can be seen from Tables3 and 4 that the repair results of the tensor method are better than the repair results of the matrix method; WNNM-RPCA and TWRPCA obtained by the weighted strategy perform better in similar methods, and the lower the noise level, the more pronounced the advantage of the weighted strategy.As mentioned above, the larger part of the singular value of the data represents the “main structure” of the data itself. At the same time, the low noise level has less influence on the main structure of the data, and the weighting strategy uses this prior. The experimental results further verified this hypothesis.


## 4. Conclusions

This study focuses on the data recovery of low-rank third-order tensors under small probability sparse noise. Tensor t-product is only one of many tensor operations. Although it has an excellent performance in some aspects, it can not achieve all aspects of transcendence. Tensor subspace has more “right shift” closeness than quantum space, but this property has not been further analyzed in combination with practice. In the face of practical problems, the theoretical analysis of this paper is relatively weak. It is hoped that there will be more in-depth theoretical research in the future, and there will be more perfect trade-off strategies for various forms of matrix or tensor operations.In data recovery, although the tensor weighting strategy proposed in this paper has brought better results, the current experiments have only achieved better results under small probability noise. Relevant experiments show that the weighting parameters are also related to the image itself, and the image information should be taken into account when determining the weighting parameters. For example, images with more details (such as texture images) and smoother images should be treated differently; in addition, the RGB image itself is regarded as a third-order low-rank tensor, and the application of weighted low rank will make the image lose some detail information while denoising. We can use the prior of nonlocal approximation for reference to aggregate the similar blocks of the image to obtain a tensor with a lower rank, and then use the corresponding algorithm to denoise. However, because TRPCA, TLRR, TWRPCA, and other methods dealing with sparse noise do not have an explicit solution, it will consume memory and greatly increase the time cost. Therefore, it is hoped that there will be a denoising algorithm that considers the image information and can estimate the noise level in the future.



---

*Source: 1920933-2022-07-20.xml*