Joint Capped Norms Minimization for Robust Matrix Recovery

1 Introduction

As a challenging machine learning problem, matrix recovery is to impute the missing entries of the given data matrix, and has many scientific applications [Srebro et al., 2004; Rennie and Srebro, 2005; Abernethy et al., 2009], such as friendship prediction in social network, rating value estimation in recommendation system and collaborative filtering, link prediction in protein-protein interaction network. As one emerging technique of compressive sensing, the problem of matrix recovery has been extensively studied on both theory and algorithms [Cand`es and Recht, 2009; Candes and Tao, 2009; Recht et al., 2010; Mazumder et al., 2009; Cai et al., 2008; Rennie and Srebro, 2005; Nie et al., 2012; 2015].

Most existing matrix recovery methods assume that the values in the data matrix are correlated and the rank of the data matrix is low. The missing entries can be recovered using the observed entries by minimizing the rank of the data matrix, which is an NP hard problem. Instead of solving this NP hard problem, the researchers minimize the trace norm (the sum of the singular values of the data matrix) as the convex relaxation of the rank function. Many recent research has been focusing on solving such trace norm minimization problem [Toh and Yun, 2010; Ji and Ye, 2009; Liu et al., 2009; Ma et al., 2009; Mazumder et al., 2009]. Meanwhile, instead of strictly keeping the values of the observed entries, the recent research work relaxed it to minimize the prediction errors (using squared error function) on the observed entries. Although the trace norm minimization based matrix recovery objective is a convex problem with global solution, the relaxation makes the final solution seriously deviate from the original one. It is desired to solve a better approximation of the rank minimization problem.

∗Corresponding Author. This work was partially supported by the U.S. NIH R01 AG049371, NSF IIS 1302675, IIS 1344152, DBI 1356628, IIS 1619308, IIS 1633753.

In this paper, we propose a novel matrix recovery model using the joint capped norms, which have been recently studied in machine learning community [Zhang, 2008; 2010; Sun et al., 2013]. First, we use the capped trace norm to approximate the rank minimization problem. Because the capped trace norm only minimizes several smallest eigen values, our new objective can approximate the rank minimization better than the trace norm. Moreover, to improve the robustness of matrix recovery method, we introduce the capped ℓ1-norm error function for the prediction errors on the observed entries. Thus, our new objective minimizes the joint capped trace norm and capped ℓ1-norm. Our objective is more robust and effective than the standard matrix recovery methods. Although our objective function is not a convex problem, we derive a new efficient optimization algorithm with rigorous convergence analysis. We evaluate our new method using both synthetic and real world data sets. The benchmark data sets from collaborative filtering and social network link prediction applications are utilized in our validations. All empirical results show our new robust matrix recovery method outperforms the standard missing value prediction approaches. In summary, we highlight the main contributions of this paper as follows:

1. We propose a novel objective function for the robust matrix recovery task using the joint capped trace norm and capped ℓ1-norm.
2. Optimizing the objective function is a non-trivial problem, thus we derive a new optimization algorithm to

solve the proposed objective with rigorous convergence analysis.

1. Our proposed new capped norm optimization algorithm is general and can be applied to solve other capped norm based problems.

2 Robust Matrix Recovery via Joint Capped Norms

2.1 Definitions of Capped ℓ1-Norm and Capped Trace Norm

The ℓ1-norm of a matrix X can be defined as ‖X‖1 = ∑i,j |xij| and the trace norm is defined as ‖X‖∗ = ∑i σi(X), where σi(X) is the i-th singular value of X. Based on these definitions, the capped ℓ1-norm of a matrix X is defined as:

and the capped trace norm is defined as:

The capped trace norm is a better approximation to rank minimization than the trace norm. When the largest singular values have large changes, the rank of the matrix could keep the same value but the trace norm will definitely change largely. Because the capped trace norm only minimizes small singular values, the capped trace norm won't have large change or even stays at the same value.

2.2 Proposed Robust Matrix RecoveryModel

Denote XΩ = {xij |(i, j) ∈ Ω}, and ‖XΩ‖2F = ∑(i,j)∈Ω x2ij . Suppose in a matrix T the observed values are TΩ = {tij |(i, j) ∈ Ω}, the matrix recovery task is to predict the unobserved values in the matrix T . This task is usually addressed by solving a rank minimization problem as follows:

To make the problem easier to solve, in practice, the rank is relaxed to the trace norm and then we solve the following relaxed problem:min

However, the relaxation makes the solution deviate seriously from the original one. Moreover, the applied squared error is sensitive to outliers.

In this paper, we use the joint capped norms to address these disadvantages in Eq. (4). First, we replace the squared F -norm loss function by the capped ℓ1-norm. As can be seen in Eq. (1), the capped ℓ1-norm can be used as a robust loss function since the function value is bounded to ε no matter how the input value deviated from zero. In practice, outliers usually make the input values largely deviate from zero, thus the bounded property in the capped norm will make it very robust to outliers. Second, we replace the trace norm by capped trace norm. As can be seen in Eq. (2), the capped trace norm is a better approximation to the rank function than trace norm does, and the large singular values have less effect in the learning.

Based on the above analysis, we propose to solve the following problem for robust matrix recovery task:

which can be written as 1

This problem looks very difficult to solve, however, inspired by the reweighted method [Nie et al., 2010; 2014; 2017], we will propose a very simple algorithm to solve it, and prove its convergence in the next section.

3 ANewAlgorithm to Solve Joint Capped Norm Optimization

3.1 Proposed Algorithm

The proposed algorithm to solve problem (6) is described in Alg. 1. Note that the problem (8) in the iteration can be easily solved and has closed form solution. The algorithm is derived from sub-gradient analysis. If the algorithm converges, the converged solution will make zero belongs to the sub-gradient of the problem (6). Therefore, the key problem is to prove the algorithm indeed converges.

Algorithm 1 Algorithm to solve the problem (6).

Initialize X.

while not converge do

1. For each (i, j) ∈ Ω, update the (i, j)-th element of S by

1. Compute the SVD of X = UΣV T . Without loss of generality, suppose the singular values σi are sorted from the smallest one to the largest one, and there are k singular values smaller than ε2. Compute D = 12 ∑ki=1 σ-1 i uiuTi .
2. Update X by the optimal solution to the problem

end while

1 In practice, to make the problem derivable, |x| and σ are replaced by √x2 + ε and √σ2 + ε, respectively. It can be seen when ε → 0, it approximates the original problem.

3.2 Proof of Convergence

Before proving the convergence of the algorithm, we prepare the following lemmas.

Lemma 1 ([Marshall et al., 2009], pages: 340) For any two hermitian matrices A,B ∈ Rn×n , suppose the eigenvalues λi(A) are sorted with same order, then we have the following inequality:

Lemma 2 Given two matrices X and ˜X, the SVD of X and ˜X are X = UΣV T and ˜X = ˜U ˜Σ˜ V T , respectively. Without loss of generality, suppose the singular values σi, ˜σi are sorted from the smallest one to the largest one respectively, and there are k singular values σi, ˜ k singular values ˜σi smaller than ε2 respectively, then we have:

Proof: Since there are ˜ k singular values ˜σi smaller than ε2, it can be easily verified that for any k and ˜ k (k ≥ ˜ k or k < ˜ k), we have ∑˜ki=1 (˜σi - ε2) ≤ ∑ki=1 (˜σi - ε2), which is equal to

Starting from (σi - ˜σi)2 ≥ 0, we have

Sum over Eq. (10) and Eq. (11) in two sides, we have

which is equal to

According to Lemma 1, we have

which is equal to

Sum over Eq. (13) and Eq. (14) in two sides, we have

Note that

According to Eq. (15) and Eq. (16), we arrive at

which is equal to Eq. (9). □

Lemma 3 Given s = { 1 2|e| , |e| < ε1 0, otherwise , we have the following inequality:

Proof: If |e| < ε1, then s = 1 2 |e|-1 . According to Lemma 2 (in the case that X and ˜X are scalar), we have min(|˜ e| , ε1)- 12 |e|-1 ˜ e2 ≤ min(|e| , ε1) - 12 |e|-1 e2 , thus Eq. (18) holds. If |e| ≥ ε1, then s = 0. Obviously, min(|˜ e| , ε1) ≤ ε1 = min(|e| , ε1) in this case, thus Eq. (18) also holds. Therefore, Eq. (18) holds in any cases. □

Now we are ready to prove the following theorem, which is the main result of this paper.

Theorem 1 Algorithm 1 will decrease the objective value of problem (6) in each iteration until it converges.

Proof: Suppose the updated X is ˜X in step 3 of Algorithm 1. Denote the SVD of X and ˜X are X = UΣV T and ˜X = ˜U ˜Σ ˜ V T , respectively. Without loss of generality, suppose the singular values σi, ˜σi are sorted from the smallest one to the largest one respectively, and there are k singular values σi, ˜ k singular values ˜σi smaller than ε2 respectively.

Since ˜X is the optimal solution to Eq. (8), we have

According to the definition of D in step 2 of Algorithm 1, Eq.(19) can be written as

According to the definition of sij in step 1 of Algorithm 1, and according to Lemma 3, we have

According to Lemma 2, we have

Sum over Eq. (20-22) in two sides, we arrive at

Since the objective value of problem (6) has a lower bound 0, the Algorithm 1 will converge, and in each iteration the objective value of problem (6) will decreased before the convergence. □

It can be checked that when the algorithm converges, the solution will satisfy the KKT conditions (derivative is zero). In the experiments we observed that the derived algorithm is very fast to converge, usually within 5-10 iterations.

4 Experiments

We evaluate our method on the following data sets: The Jester Jokes data sets [Goldberg et al., 2001] 1 , Wikipedia [Leskovec et al., 2009] and Epinions [Massa and Avesani, 2006] data sets 2 and Sweetrs data set 3 . There are 7 compared matrix recovery methods in total: SVD, SVT [Cai et al., 2008], RRMC [Huang et al., 2013], ALM [Lin et al., 2010], GROUSE [Balzano et al., 2010], OPTSPACE [Keshavan and Oh, 2009] and our method. In our experiments, all the parameters are selected via 5-fold cross validation to guarantee their best performance. Normalized root mean square error (nRMSE) and normalized mean absolute error (nMAE) are used as evaluation metrics.

1 http://eigentaste.berkeley.edu/dataset/

2 http://snap.stanford.edu/data/

3 http://sweetrs.org

4.1 Experiments on Real World Data Sets

Jester Jokes Rating Prediction

Firstly, we present experiment results on Jester Jokes data sets. To make this problem easy to evaluate, we select a part of the most active users from the original data. The sizes of matrix for these three data sets are 10000 × 100, 13109 × 140 and 13449 × 140. In the experiments, we assume 5%, 10%, 15% and 20% ratings of each matrix are known respectively. In each case, training data are selected randomly, and the whole procedure is repeated for 5 times randomly to compute the average performance.

The results of matrix recovery task on Jester jokes data are shown in Table 1. In real life, users are very likely to read just some of the jokes and to rate even fewer. From Table 1, obviously our method could make use of sparse training data, and outperforms other methods in all different cases.

In reference to our objective function, there are three parameters to tune, ε1, ε2 and γ. Fig. 1 shows the relationship between ε1, ε2 and γ with performance evaluation metric nMAE. In the experiment, we fix two parameters and change another one. Fig. 1a shows that in this occasion, ε1 plays a insignificant role when there are few outliers. Fig. 1b shows that ε2 is the most important parameter in this model, for it determines the rank of the matrix indirectly. In our experiments, we input a hypothetical rank value, and the value of the ε2 is selected based on the singular values of the matrix in the first 5 iterations. After that, ε2 is fixed to be a constant. In this way, our model can learn a proper value of ε2 automatically in different situations. It is also very interesting to find out through Fig. 1c that the value of γ also doesn't matter too much on the performance of the model in Jester Jokes data sets.

Social Network Linking Prediction

In this section, we show the results of matrix recovery algorithms in predicting social network linking data, Wikipedia and Epinions. In this experiment, in order to alleviate the data skewness and keep the computation manageable, we select top 2,000 highest degree users from each data set. In these experiments, we assume 10% entries of each matrix are known, and the other 90% information are used as testing data.

From Table 2, we can observe that our cRMC method outperforms others in terms of nRMSE and nMAE on both of the two social network trust matrix. Then, we can make use of the prediction matrix to make recommendations. A better recommendation always means better user experience, and it may lead to much profit for these internet enterprises.

Sweetrs Rating Prediction

In this section, we present experiment results on Sweetrs data set. In this data set, the size of the matrix is 390 × 47, and we let 10% ratings as training data. Table 2 shows the results of our experiment on Sweetrs data. In the experiment, ALM breaks down during training, hence we ignore this method. In this table, we can find out that the performance of our method is better than the other ones in this case.

4.2 Robustness Evaluation on Synthetic Noise Data

In real life, it usually happens that some users click the wrong ratings by accident or there are even some users who make vicious ratings on purpose. If a method can't deal with these noisy ratings properly, a terrible model will be generated and it may lead to unexpected loss.

To evaluate the robustness of our method and prove its strong ability to deal with outliers, we perform experiments on Jokes and Sweetrs data sets. We impose noise to the observed data from 0% to 5% each time, and all these noises are set to be the largest or the lowest value randomly. In the experiments, we assume 10% of the ratings are known.

In the experiment, bad ratings are treated as outliers. It is obvious that our objective function explicitly take the unclean training data into consideration, and the value of ε1 is used to leave out the outliers. In this way, we protect the matrix's original low-rank structure from being distorted.

From Fig. 2, we can see that when the noise increases, the prediction accuracy of all methods tend to degenerate slightly and outliers distort the low-rank structure of the original matrix. It is easy to observe our method outperforms other methods consistently, while the percentage of the noise increases from 0% to 5%. It is well proved from these experiments that our method can deal with outliers properly, and keep the correct low-rank structure of a matrix.

5 Conclusions

In this paper, we proposed a new robust matrix recovery method using joint capped trace norm and capped ℓ1-norm. Our capped trace norm can approximate the rank minimization problem tighter than the trace norm to achieve better matrix recovery results. The capped ℓ1-norm based error function enhances the robustness of the proposed objective. Both capped trace norm and capped ℓ1-norm are non-smooth non-convex. To solve this difficult optimization problem, we proposed a new optimization algorithm with rigorous convergence analysis. The evaluation experiments were performed on both synthetic and real world applications (collaborative filtering and social network link prediction) data. All empirical results demonstrate the effectiveness of the proposed robust matrix recovery model.