# A Singular Value Thresholding with Diagonal-Update Algorithm for Low-Rank Matrix Completion

Authors: Yong-Hong Duan; Rui-Ping Wen; Yun Xiao
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The singular value thresholding (SVT) algorithm plays an important role in the well-known matrix reconstruction problem, and it has many applications in computer vision and recommendation systems. In this paper, an SVT with diagonal-update (D-SVT) algorithm was put forward, which allows the algorithm to make use of simple arithmetic operation and keep the computational cost of each iteration low. The low-rank matrix would be reconstructed well. The convergence of the new algorithm was discussed in detail. Finally, the numerical experiments show the effectiveness of the new algorithm for low-rank matrix completion.


---

## Body

## 1. Introduction

The problem of completing low-rank and sparse matrices from some of its observed entries occurs frequently in many areas of engineering and applied science such as machine learning [1, 2], model reduction [3], compressed sensing [4], control [5], pattern recognition [6], signal and imaging inpainting [7–10], and computer vision [11]. From the pioneering work on low-rank approximation by Fazel [12] as well as on matrix completion by Candès and Recht [13], there has been a lot of study (see [1–35] and references therein) both from theoretical and algorithmic aspects on the problem of recovering a low-rank matrix from partial entries, also known as matrix completion. There is a rapidly growing interest for this issue. Explicitly seeking the lowest rank matrix consistent with the known entries is mathematically expressed as(1)minX∈ℜm×nrankX,s.t.pΩX=pΩM,where the matrix M∈ℜm×n is the underlying matrix to be reconstructed and pΩ is the associated sampling orthogonal projection operator which acquires only the entries indexed by Ω⊂1,2,…,m×1,2,…,n with Ω is a random subset of indices for the known entries.The general problem (1), however, is nonconvex and is NP hard [14] due to the rank objective. There are a few of algorithms for solving this model directly. Alternatively, Candès and Rechat [13] switched (1) to another simple convex optimization problem (2) as follows:(2)minX∈ℜm×nX∗,s.t.pΩX=pΩM,where the nuclear norm X∗ is the sum of all singular values of the matrix X.Furthermore, it has proved that the sequenceXk converges to the unique solution of the following optimization problem closely related to (2) in [15]:(3)minX∈ℜm×nτX∗+12XF2.s.t.pΩX=pΩM.As for the solution of problems (2) and (3), there have been many computational efficient algorithms which are designed for a broad class of matrices such as mainly the accelerated proximal gradient (APG) algorithm [16], the augmented Lagrange multiplier (ALM) algorithm [17], several methods [18–21] resulted in alternating optimization based on the bilinear factorization M=XY with X∈ℜm×r,Y∈ℜr×n and rank M=r, and the singular value theresholding (SVT) algorithm, as well as its improvements [15, 22–24]. However, the computations of partial singular value decomposition (SVD) were required at each iteration in the most direct implementation of these algorithms. The computational cost of computing the SVD has complexity of On3 when the rank r and matrix-size n are proportional, resulting in computing the SVD to be the dominant computational cost at each iteration and then limits their applicability for large n. In view of its outstanding performance and elegant mathematical properties, the SVT algorithm obtains widespread attention [25–27]. The variants and extended applications of the SVT algorithm have been studied later: Candès et al. [28] presented a unbiased risk estimate formula of the SVT for the noisy observations; Chatterjee [29] studied a general method for matrix denoising using SVT, which covers the stochastic block model as a special case; Donoho and Gavish [30] pointed out several ways that these matrix denoising results for singular value soft thresholding (SVST) estimation of low-rank matrices parallel results for soft thresholding of sparse vectors; Dutta et al. [31] proposed an alternative solution to the sensitivity of the classical principal component analysis (PCAs) to the outliers for solving the problem(4)minX∈ℜm×n12M−XWF2+τX∗,with the nonsingular weight matrix W∈ℜn×m which is user provided or automatically inferred from the data, called as WSVT problem; Klopp [32] introduced a variant of the SVT iteration; Ma and Xu [33] recovered the received signal strength (RSS) reading and achieve good localization performance based on the SVT theory; Zhang et al. [34] put forward a lower bound guaranteeing exact matrix completion via the SVT algorithm; Zhang et al. [35] have considered the low-rank tensor completion problem through a hybrid singular value thresholding scheme.This paper develops a modification of the SVT algorithm for approximately solving the nuclear norm minimization problem (2). By using a diagonal-update technique for the approximated sequence at each step, the iteration matrices generated by the new algorithm are approximated to the true solution well, which saves significant computational cost of the SVT algorithm performance. And we also establish the convergence theory in detail. Experimental results show that the new algorithm outperforms the standard SVT and its several variants algorithms, especially when problem (2) comes to large-scale issues.The rest of the paper is organized as follows. After we provide some notations in this section, we review briefly the standard SVT algorithm, the accelerated singular value thresholding (ASVT) algorithm as well as its modification, and a modified algorithm of the SVT algorithm with diagonal-update (D-SVT) is proposed in Section2. In Section 3, the convergence theory of the new algorithm is established. Then, numerical experiments are shown and compared in Section 4. Finally, we end the paper with the concluding remarks in Section 5.Here are some notations.ℜm×n denotes m×n real matrices set, ℜ+m×n represents the m×n nonnegative and real matrices’ set. The nuclear norm X∗ of a matrix X is defined by X∗=∑k=1rσkX,σkX denotes the kth largest singular value of the real matrix X∈ℜm×n of rank r, and the Frobenius norm XF of a matrix X=xij∈ℜm×n is XF=∑i=1m∑j=1nxij21/2=traceATA. XT is the transpose of a matrix X. X,Y=traceXTY denotes the inner product between two matrices. Ω⊂1,2,…,m×1,2,…,n is the indices of the observed entries, and Ω¯ is the complementary set of Ω. pΩ is the orthogonal projector onto Ω, satisfying,(5)pΩX=Xij,i,j∈Ω,0,i,j∉Ω.


## 2. Related Algorithms

In order to completing comparison subsequently, we briefly review and introduce some algorithms for solving the matrix completion problem (2).


### 2.1. The Standard Singular Value Thresholding (SVT) Algorithm

Definition 1.
The singular value decomposition (SVD) of a matrixX∈ℜm×n of rank r is(6)X=UΣrVT,Σr=diagσ1,…,σr,where U∈ℜm×r and V∈ℜn×r are two orthogonal matrices, σ1≥σ2≥⋯≥σr>0.Definition 2 (see [15]).
For eachτ≥0, the singular value thresholding operator DτX is defined as follows, say the “shrinkage”:(7)DτX≔UDτΣrVT,DτΣr=diagσi−τ+,where σi−τ+=σi−τ,ifσi>τ,0,ifσi≤τ.
The standard SVT algorithm proposed in [15] is a solution for solving the convex optimization (2).Algorithm 1: Singular value thresholding (SVT) algorithm, algorithm 1 of [15].
Input: sampled set Ω and sampled entries pΩM, step size δ∈0,2, tolerance ε, parameter τ>0, increment ℓ, and maximum iteration count kmaxOutput:XoptDescription: recover a low-rank matrix M from a subset of sampled entries(1)
SetY0=k0δpΩM, k0 is an integer with τ/δpΩM2∈k0−1,k0(2)
Setr0=0(3)
fork=1 to kmax(4)
Setsk=rk−1+1(5)
repeat(6)
ComputeUk−1,Σk−1,Vk−1sk(7)
Setsk=sk+ℓ(8)
untilσsk−ℓk−1≤τ(9)
Setrk=maxj:σjk−1>τ(10)
SetXk=∑j=1rkσjk−1−τujk−1vjk−1(11)
ifpΩXk−MF<εpΩMFthen break(12)
SetYijk=Yijk−1+δMij−Xijk,ifi,j∈Ω,0,ifi,j∉Ω(13)
endfork(14)
SetXopt=XkRemark 1.
Due to the ability of producing low-rank solutions with the soft-thresholding operator, the SVT algorithm was shown to be extremely efficient at addressing problems with low-rank optimal solutions such as recommender systems.


### 2.2. The Accelerated Singular Value Thresholding (ASVT) Algorithm

Introduce the Lagrangian function of problem (3) as(8)ℒX,Y=τX∗+Y,pΩM−X+12XF2,where Y is the Lagrangian variable.In terms of the dual approach,fY=infXℒX,Y is the dual function of ℒX,Y, which is concave. Define(9)hY=−fY=−τDτpΩY∗+Y,pΩM−DτpΩY+12DτpΩYF2,which is convex. Thus, we can solve problem (3) by firstly minimizing the objective function hY, namely,(10)minY∈ℜm×nhY.Problem (10) was computed via Nesterov’s method with an adaptive line search scheme. Then, Algorithm 2 has been provided.Algorithm 2: The adaptive linear search scheme, algorithm 1 of [22].
Input:μ˜,α−1=0.5,Y−1=Y0,L−1=L0,γ0≥μ˜,λ0=1Output:YN(1)
fork=0,1 to Ndo(2)
while 1 do(3)
Computeαk∈0,1 as the root of Lkαk2=1−αkγk+αkμ˜(4)
Computeγk+1=1−αkγk+αkμ˜,βk=γk1−αk−1/αk−1γk+Lkαk(5)
ComputeSk=Yk+βkYk−Yk−1(6)
ComputeYk+1=Sk−1/Lkh′Sk(7)
ifhYk+1≤hSk−1/2Lkh′SkF2then(8)
go to Line 13(9)
else(10)
Lk=2Lk(11)
end if(12)
end while(13)
Setω=2LkhSk−hYk+1/h′SkF2,Lk+1=hωLk,hω=1,if1≤ω≤5,0.8,ifω>5(14)
Setλk+1=1−αkλk(15)
end forBased on the above, the accelerated singular value thresholding (ASVT) algorithm has been proposed in [22]. Furthermore, Wang et at. [23] presented the Ne-SVT by replacing the adaptive linear search with Nemirovski’s technique and the M-ASVT algorithms by using the same search technique in the ASVT algorithm. The overall steps of the later can be organized as Algorithm 3.Algorithm 3: The modified ASVT (m-asvt) algorithm, algorithm 1 of [23]
Input:L1,t−1=0,t0=1,Y1=Y0=0,η∈0,1Output:YN+1,XN+1=DτpΩYN+1Description: recover a low-rank matrix Y(1)
fork=1,2,…,Ndo(2)
Computek=1,2,…,N(3)
ComputeSk=Yk+βkYk−Yk−1(4)
while 1 do(5)
ComputeYk+1=Sk−1/Lkh′Sk(6)
ifhYk+1≤hSk−1/2Lkh′SkF2then(7)
Lk+1=ηLk, go to Step 1(8)
else(9)
Lk=2Lk(10)
end if(11)
end while(12)
Settk=1+1+4tk−12/2(13)
end forIt is reported that M-ASVT needs much fewer iterations than ASVT algorithm under the same level of accuracy and the same cost of computing.


### 2.3. The Singular Value Thresholding with Diagonal-Update (D-SVT) Algorithm

We are now in the position to introduce a modified singular value thresholding algorithm by using a diagonal-update technique, as shown in Algorithm4.Algorithm 4: Singular value thresholding with diagonal-update (D-SVT) algorithm, Algorithm 1 of [15]
Input: sampled set Ω and sampled entries pΩM, step size δ∈0,2, tolerance ε, parameter τ>0, increment ℓ, and maximum iteration count kmaxOutput:XoptDescription: recover a low-rank matrix M from a subset of sampled entries(1)
SetY0=k0δpΩM, k0 is an integer with τ/δpΩM2∈k0−1,k0(2)
Setr0=0(3)
fork=1 to kmax(4)
Setsk=rk−1+1(5)
repeat(6)
ComputeUk−1,Σk−1,Vk−1sk(7)
Setsk=sk+ℓ(8)
untilσsk−ℓk−1≤τ(9)
Setrk=maxj:σjk−1>τ(10)
SetX˜k=∑j=1rkσjk−1−τujk−1vjk−1(11)
ComputeWk=argminWpΩM−pΩX˜kWkF(12)
SetXk=pΩX˜kWk(13)
ifpΩXk−MF<εpΩMFthen break(14)
SetYijk=Yijk−1+δMij−Xijk,ifi,j∈Ω,0,ifi,j∉Ω(15)
endfork(16)
SetXopt=XkSetD:=pΩX˜k for short. The difference with the standard SVT algorithm may seem at k th step, replacing the iteration matrix X˜k with the diagonal-update DWk of its projector D, where Wk=diagw11k,w22k,…,wnnk∈ℜ+n×n is obtained by(11)Wk=argminWpΩM−DWF.Equation (11) is easy to compute since it is so simple just some arithmetic operation required, without extra cost. In fact, the exact solution of (11) is given by(12)wjjk=M:,j,Xk:,jXk:,j,Xk:,j,j=1,2,…,n.Remark 2.
The sequence matrices generated by the new algorithm are approximated to the true solution well, which saves significant computational cost of the SVT algorithm performance, without actually extra complexity. It is designed as Algorithm4 by plugging some steps into the SVT method. It should be seen that Algorithm 4 has three lines (as shown in lines 10–12) more than Algorithm 1. The new algorithm includes Algorithm 1 as special case when W=I.


## 2.1. The Standard Singular Value Thresholding (SVT) Algorithm

Definition 1.
The singular value decomposition (SVD) of a matrixX∈ℜm×n of rank r is(6)X=UΣrVT,Σr=diagσ1,…,σr,where U∈ℜm×r and V∈ℜn×r are two orthogonal matrices, σ1≥σ2≥⋯≥σr>0.Definition 2 (see [15]).
For eachτ≥0, the singular value thresholding operator DτX is defined as follows, say the “shrinkage”:(7)DτX≔UDτΣrVT,DτΣr=diagσi−τ+,where σi−τ+=σi−τ,ifσi>τ,0,ifσi≤τ.
The standard SVT algorithm proposed in [15] is a solution for solving the convex optimization (2).Algorithm 1: Singular value thresholding (SVT) algorithm, algorithm 1 of [15].
Input: sampled set Ω and sampled entries pΩM, step size δ∈0,2, tolerance ε, parameter τ>0, increment ℓ, and maximum iteration count kmaxOutput:XoptDescription: recover a low-rank matrix M from a subset of sampled entries(1)
SetY0=k0δpΩM, k0 is an integer with τ/δpΩM2∈k0−1,k0(2)
Setr0=0(3)
fork=1 to kmax(4)
Setsk=rk−1+1(5)
repeat(6)
ComputeUk−1,Σk−1,Vk−1sk(7)
Setsk=sk+ℓ(8)
untilσsk−ℓk−1≤τ(9)
Setrk=maxj:σjk−1>τ(10)
SetXk=∑j=1rkσjk−1−τujk−1vjk−1(11)
ifpΩXk−MF<εpΩMFthen break(12)
SetYijk=Yijk−1+δMij−Xijk,ifi,j∈Ω,0,ifi,j∉Ω(13)
endfork(14)
SetXopt=XkRemark 1.
Due to the ability of producing low-rank solutions with the soft-thresholding operator, the SVT algorithm was shown to be extremely efficient at addressing problems with low-rank optimal solutions such as recommender systems.


## 2.2. The Accelerated Singular Value Thresholding (ASVT) Algorithm

Introduce the Lagrangian function of problem (3) as(8)ℒX,Y=τX∗+Y,pΩM−X+12XF2,where Y is the Lagrangian variable.In terms of the dual approach,fY=infXℒX,Y is the dual function of ℒX,Y, which is concave. Define(9)hY=−fY=−τDτpΩY∗+Y,pΩM−DτpΩY+12DτpΩYF2,which is convex. Thus, we can solve problem (3) by firstly minimizing the objective function hY, namely,(10)minY∈ℜm×nhY.Problem (10) was computed via Nesterov’s method with an adaptive line search scheme. Then, Algorithm 2 has been provided.Algorithm 2: The adaptive linear search scheme, algorithm 1 of [22].
Input:μ˜,α−1=0.5,Y−1=Y0,L−1=L0,γ0≥μ˜,λ0=1Output:YN(1)
fork=0,1 to Ndo(2)
while 1 do(3)
Computeαk∈0,1 as the root of Lkαk2=1−αkγk+αkμ˜(4)
Computeγk+1=1−αkγk+αkμ˜,βk=γk1−αk−1/αk−1γk+Lkαk(5)
ComputeSk=Yk+βkYk−Yk−1(6)
ComputeYk+1=Sk−1/Lkh′Sk(7)
ifhYk+1≤hSk−1/2Lkh′SkF2then(8)
go to Line 13(9)
else(10)
Lk=2Lk(11)
end if(12)
end while(13)
Setω=2LkhSk−hYk+1/h′SkF2,Lk+1=hωLk,hω=1,if1≤ω≤5,0.8,ifω>5(14)
Setλk+1=1−αkλk(15)
end forBased on the above, the accelerated singular value thresholding (ASVT) algorithm has been proposed in [22]. Furthermore, Wang et at. [23] presented the Ne-SVT by replacing the adaptive linear search with Nemirovski’s technique and the M-ASVT algorithms by using the same search technique in the ASVT algorithm. The overall steps of the later can be organized as Algorithm 3.Algorithm 3: The modified ASVT (m-asvt) algorithm, algorithm 1 of [23]
Input:L1,t−1=0,t0=1,Y1=Y0=0,η∈0,1Output:YN+1,XN+1=DτpΩYN+1Description: recover a low-rank matrix Y(1)
fork=1,2,…,Ndo(2)
Computek=1,2,…,N(3)
ComputeSk=Yk+βkYk−Yk−1(4)
while 1 do(5)
ComputeYk+1=Sk−1/Lkh′Sk(6)
ifhYk+1≤hSk−1/2Lkh′SkF2then(7)
Lk+1=ηLk, go to Step 1(8)
else(9)
Lk=2Lk(10)
end if(11)
end while(12)
Settk=1+1+4tk−12/2(13)
end forIt is reported that M-ASVT needs much fewer iterations than ASVT algorithm under the same level of accuracy and the same cost of computing.


## 2.3. The Singular Value Thresholding with Diagonal-Update (D-SVT) Algorithm

We are now in the position to introduce a modified singular value thresholding algorithm by using a diagonal-update technique, as shown in Algorithm4.Algorithm 4: Singular value thresholding with diagonal-update (D-SVT) algorithm, Algorithm 1 of [15]
Input: sampled set Ω and sampled entries pΩM, step size δ∈0,2, tolerance ε, parameter τ>0, increment ℓ, and maximum iteration count kmaxOutput:XoptDescription: recover a low-rank matrix M from a subset of sampled entries(1)
SetY0=k0δpΩM, k0 is an integer with τ/δpΩM2∈k0−1,k0(2)
Setr0=0(3)
fork=1 to kmax(4)
Setsk=rk−1+1(5)
repeat(6)
ComputeUk−1,Σk−1,Vk−1sk(7)
Setsk=sk+ℓ(8)
untilσsk−ℓk−1≤τ(9)
Setrk=maxj:σjk−1>τ(10)
SetX˜k=∑j=1rkσjk−1−τujk−1vjk−1(11)
ComputeWk=argminWpΩM−pΩX˜kWkF(12)
SetXk=pΩX˜kWk(13)
ifpΩXk−MF<εpΩMFthen break(14)
SetYijk=Yijk−1+δMij−Xijk,ifi,j∈Ω,0,ifi,j∉Ω(15)
endfork(16)
SetXopt=XkSetD:=pΩX˜k for short. The difference with the standard SVT algorithm may seem at k th step, replacing the iteration matrix X˜k with the diagonal-update DWk of its projector D, where Wk=diagw11k,w22k,…,wnnk∈ℜ+n×n is obtained by(11)Wk=argminWpΩM−DWF.Equation (11) is easy to compute since it is so simple just some arithmetic operation required, without extra cost. In fact, the exact solution of (11) is given by(12)wjjk=M:,j,Xk:,jXk:,j,Xk:,j,j=1,2,…,n.Remark 2.
The sequence matrices generated by the new algorithm are approximated to the true solution well, which saves significant computational cost of the SVT algorithm performance, without actually extra complexity. It is designed as Algorithm4 by plugging some steps into the SVT method. It should be seen that Algorithm 4 has three lines (as shown in lines 10–12) more than Algorithm 1. The new algorithm includes Algorithm 1 as special case when W=I.


## 3. Convergence Analysis

In this section, the convergence theory is discussed for the singular value thresholding which involves diagonal-update algorithm.Theorem 1.
Suppose thatpΩX˜kI−Wkk=1∞ is uniformly bounded. Then,(13)limk⟶∞pΩM−Xk=limk⟶∞pΩM−X˜k=0.Proof.
It follows from Algorithm4 that(14)Yk−pΩM=Yk−1−pΩM+δkpΩM−pΩXk=1−δkYk−1−pΩM+δkYk−1−pΩXk=1−δkYk−1−pΩM+δkYk−1−pΩX˜k+pΩX˜k−pΩXk=1−δkYk−1−pΩM+δkYk−1−pΩX˜k+δkpΩX˜k−Xk.
In term of the assumption of this theorem,∀k,∃Θ such that(15)pΩX˜kI−WkF≤Θholds true.
LetZk=:Yk−pΩM. We note that Xk=pΩX˜kWk from Algorithm 4, and by substituting the following inequalities(16)pΩYk−1−X˜kF≤Yk−1−X˜kF≤nτ,pΩX˜k−XkF=pΩX˜kI−WkF≤Θ,we have(17)ZkF≤1−δkZk−1F+δknτ+δkΘ≤⋯≤∏i=1k1−δiZ0F+∑i=1k∏j=1i1−δjδinτ+δiΘ≤ckZ0F+∑i=1kciδinτ+M,if1−δi≤c<1≤ckZ0F+21−cnτ+M.
Hence,Zkk=1∞ is bounded and so is Ykk=1∞.
Moreover, it is obtained that(18)limi⟶∞pΩM−Xi=0,from the equation(19)Yk=∑i=1kδipΩM−Xi.
Moreover,(20)limi⟶∞pΩM−X˜i=0,since limk⟶∞Wk=I. The theorem has been proved.Theorem 2.
LetX†,τ be the limiting point of the sequence Xk generated by Algorithm 4. Then, X†,τ is the solution of the optimization problem (3).Proof.
It is obtained thatX˜k is the optimal solution of (8) for that value of Yk−1 from Algorithm 4.
Hence, for any feasible matrixX, it is yielded that(21)τX∗+12XF2≥ℒX˜k,Yk−1≥limk⟶∞ℒX˜k,Yk−1=ℒX†,τ,Y†,τ=τX†,τ∗+12X†,τF2.
Thus,X†,τ is the unique solution of (3).Theorem 3.
Suppose thatlimτ⟶∞X†,τ=X†. Then, X† is the optimal solution of the optimization problem (2).Proof.
Note thatX† is the optimal solution of the optimization problem (2) if and only if(22)0∈pΩ¯∂X†∗.
From Theorem2, we have(23)0∈pΩ¯τ∂X†,τ∗+X†,τ,which implies that(24)0∈pΩ¯∂X†,τ∗+1τX†,τ.
Therefore,(25)limτ⟶∞1τX†,τ=0,since X† is bounded. Thus,(26)0∈pΩ¯∂X†∗.


## 4. Numerical Experiments

In this section, we provide the performance of our D-SVT algorithm in comparison with the SVT, ASVT, and M-ASVT algorithms mentioned inSection 2 and report the running time in seconds (denoted by “time (s)”), the numbers of iterations (denoted by “IT”) it takes to reach convergence, and the relative errors of the reconstruction (denoted by” Error 1 and Error 2″) as follows:(27)Error1=Xk−pΩMFpΩMF,Error2=XkWk−MFMF.All the experiments are conducted on the same workstation with an Intel (R) Core (TM) i7-6700 CPU @3.40GHZ that has 16 GB memory and 64 bit operating system, running Windows 7, and Matlab (vision 2016a). For conciseness, the tests presented consider square matrices as is typical in the study. That is to say, suppose to simplify that the unknown matrixM∈ℜn×n is square and that one has available s sampled entries Mij:i,j∈Ω, where Ω is a random subset of cardinality s. By the way, the iteration fails if the number of iterations is up to 1000.In our implement, we generaten×n matrices of rank r by sampling uniformly at random among all sets of cardinality s; then, p=s/n2 denotes the observation ratio. Let ε=2×10−4. As discussed earlier [15], δ=1.2p−1 and the step sizes are constant and the parameter τ is chosen empirically. And as presented earlier [23], the parameters L1=1andη=0.8. As for D-SVT algorithm, we choose δ=1.68p−1, and τ is the same as the SVT algorithm.The tested matrix dimensions (denoted by “size (n)”) are from 1,000 to 12,000. The experimental results are shown in Tables1–6. Our experiments suggest that Algorithm 4 is fast and significantly outperforms the other algorithms in terms of both number of iteration steps and computing time. The new algorithm is especially well suited for problems of very large sizes.Table 1
Computational results for small-size problems whenτ=5n.
UnknownMComputational resultsSize (n)Rank (r)pAlgorithmITTime (s)Error 1Error 21,000200.20SVT275101.69011.9826e − 043.2515e − 04ASVT26797.72111.0021e − 041.8735e − 04M-ASVT25186.52381.2541e − 042.3361e − 04D-SVT18671.09871.9793e − 043.1915e − 041,000300.30SVT25588.28531.9663e − 043.0680e − 04ASVT24883.21581.0002e − 042.1714e − 04M-ASVT22980.26551.3326e − 041.9855e − 04D-SVT17070.05491.9705e − 043.0682e − 042,000300.15SVT271837.70411.9803e − 043.2390e − 04ASVT266821.45541.0204e − 042.1444e − 04M-ASVT258799.89851.2130e − 042.2225e − 04D-SVT182675.13721.9687e − 043.1833e − 042,000400.20SVT262783.20101.9843e − 043.1685e − 04ASVT248766.12471.0203e − 041.5682e − 04M-ASVT233758.12131.8860e − 042.3310e − 04D-SVT165619.67301.9892e − 043.1476e − 043,000300.10SVT2762758.21.9699e − 043.2527e − 04ASVT2652710.22361.0007e − 041.9985e − 04M-ASVT2602681.28741.5623e − 042.1414e − 04D-SVT1852076.11.9885e − 043.2650e − 043,000400.13SVT2672692.51.9609e − 043.1899e − 04ASVT2612551.44781.0014e − 041.8569e − 04M-ASVT2552432.12781.7784e − 042.3369e − 04D-SVT1742105.31.9943e − 043.2126e − 043,000500.17SVT2592670.61.9688e − 043.1486e − 04ASVT2542641.25871.0012e − 042.3331e − 04M-ASVT2392598.56231.7456e − 042.2114e − 04D-SVT1622092.81.9611e − 043.1200e − 044,000300.07SVT27667931.9824e − 043.2954e − 04ASVT27066591.0040e − 042.3322e − 04M-ASVT26165551.9998e − 042.2288e − 04D-SVT1865409.11.9823e − 043.2674e − 044,000400.10SVT2716184.31.9895e − 043.2622e − 04ASVT27661551.1012e − 042.1170e − 04M-ASVT26960991.9963e − 042.0208e − 04D-SVT1805289.61.9689e − 043.2015e − 044,000500.12SVT2696296.31.9889e − 043.2247e − 04ASVT2636241.21.0500e − 041.5589e − 04M-ASVT2606258.21.1010e − 041.6601e − 04D-SVT1864687.21.9802e − 043.1833e − 04Table 2
Computational results for small-size problems whenτ=4n.
UnknownMComputational resultsSize (n)Rank (r)pAlgorithmITTime (s)Error1Error 21,000200.20SVT22376.35531.9830e − 043.2593e − 04ASVT20671.22891.0054e − 041.9965e − 04M-ASVT19469.55631.10231.9877e − 04D-SVT15666.94871.9748e − 043.2191e − 041,000300.30SVT20770.39921.9988e − 043.1406e − 04ASVT20068.22411.1145e − 042.1365e − 04M-ASVT19263.22891.0089e − 042.0005e − 04D-SVT14461.42861.9333e − 043.0025e − 042,000300.15SVT220712.94931.9956e − 043.2718e − 04ASVT217704.33651.0203e − 042.1475e − 04M-ASVT211699.37851.0057e − 042.0624e − 04D-SVT152535.28461.9969e − 043.2316e − 042,000400.20SVT212644.30271.9890e − 043.1802e − 04ASVT205634.98701.1110e − 042.3875e − 04M-ASVT199618.99521.0074e − 042.2271e − 04D-SVT148522.82931.9969e − 043.1650e − 043,000300.10SVT2242248.91.9831e − 043.2891e − 04ASVT2182213.41.3354e − 042.6522e − 04M-ASVT2112168.81.1532e − 042.3301e − 04D-SVT1581824.81.9718e − 043.2220e − 043,000400.13SVT2162222.41.9616e − 043.1860e − 04ASVT2072025.31.1004e − 042.3110e − 04M-ASVT2011999.21.2121e − 042.5403e − 04D-SVT1521807.71.9394e − 043.1228e − 043,000500.17SVT2112234.11.9597e − 043.1398e − 04ASVT2042106.41.1140e − 042.5510e − 04M-ASVT1981999.41.0042e − 042.1030e − 04D-SVT1481733.61.9507e − 043.1039e − 044,000300.07SVT2245314.01.9728e − 043.2816e − 04ASVT2185127.11.2544e − 042.3365e − 04M-ASVT2095001.21.1004e − 041.9952e − 04D-SVT1604324.11.9500e − 043.2075e − 044,000400.10SVT2185209.71.9845e − 043.2463e − 04ASVT2115101.01.1140e − 042.0407e − 04M-ASVT2054998.21.0045e − 041.8854e − 04D-SVT1554237.71.9460e − 043.1656e − 044,000500.12SVT2155114.31.9847e − 043.2178e − 04ASVT2075003.51.6652e − 042.3310e − 04M-ASVT2004889.21.1143e − 042.1113e − 04D-SVT1514068.91.9986e − 043.2133e − 04Table 3
Computational results for small-size problems whenτ=3n.
UnknownMComputational resultsSize (n)Rank (r)pAlgorithmITTime (s)Error 1Error 21,000200.198SVT17258.93241.9708e − 043.2399e − 04ASVT16555.32111.2114e − 042.1140e − 04M-ASVT16051.33331.1002e − 042.0047e − 04D-SVT11950.80261.9333e − 043.1028e − 041,000300.2955SVT15855.61211.9651e − 043.0783e − 04ASVT15051.33611.2254e − 042.5512e − 04M-ASVT14348.22101.1102e − 042.0005e − 04D-SVT11048.31591.9430e − 043.0057e − 042,000300.1489SVT169509.36631.9555e − 043.1915e − 04ASVT161500.23691.2323e − 041.9985e − 04M-ASVT156498.23231.1110e − 041.8541e − 04D-SVT117410.19591.9399e − 043.1251e − 042,000400.198SVT163491.45691.9544e − 043.1199e − 04ASVT157482.31451.3324e − 042.5666e − 04M-ASVT152469.22211.1142e − 042.1104e − 04D-SVT113399.21431.9981e − 043.1611e − 043,000300.0995SVT1731810.31.9523e − 043.2420e − 04ASVT1661796.21.5562e − 042.0004e − 04M-ASVT1591652.81.1124e − 041.8989e − 04D-SVT1191386.71.9967e − 043.2635e − 043,000400.1324SVT1661713.31.9533e − 043.1671e − 04ASVT1591695.21.5252e − 042.8485e − 04M-ASVT1541666.31.2235e − 042.1103e − 04D-SVT1161355.31.9953e − 043.2249e − 043,000500.1653SVT1621664.91.9418e − 043.1127e − 04ASVT1571662.31.6523e − 042.1104e − 04M-ASVT1571660.21.0023e − 042.1001e − 04D-SVT1131333.31.9641e − 043.1282e − 044,000300.0747SVT1744112.21.9442e − 043.2322e − 04ASVT1704000.31.1115e − 042.1104e − 04M-ASVT1683995.21.0002e − 041.9952e − 04D-SVT1203247.91.9820e − 043.2760e − 044,000400.0995SVT1684023.71.9513e − 043.1937e − 04ASVT1633998.21.6674e − 042.5510e − 04M-ASVT1593885.11.3114e − 042.0047e − 04D-SVT1173056.11.9684e − 043.1983e − 044,000500.1242SVT1653803.51.9604e − 043.1727e − 04ASVT1603685.21.2246e − 042.8525e − 04M-ASVT1563459.21.1006e − 042.1139e − 04D-SVT1153104.31.9875e − 043.1965e − 04Table 4
Computational results for large-size problems whenτ=5n.
UnknownMComputational resultsSize (n)Rank (r)pAlgorithmITTime (s)Error 1Error 25,000400.08SVT271123341.9826e − 043.2645e − 04ASVT266123011.2225e − 042.1147e − 04M-ASVT264122951.0558e − 042.0036e − 04D-SVT1909845.81.9556e − 043.1916e − 045,000500.10SVT265115051.9898e − 043.2434e − 04ASVT263114271.2558e − 043.0001e − 04M-ASVT260115821.1010e − 042.5563e − 04D-SVT1869312.21.9976e − 043.2374e − 045,000600.12SVT262119831.9795e − 043.1961e − 04ASVT259118861.5252e − 042.5474e − 04M-ASVT256119631.1023e − 042.1136e − 04D-SVT1859656.41.9581e − 043.1450e − 048,000500.06SVT269486991.9902e − 043.2707e − 04ASVT263499871.1298e − 042.6634e − 04M-ASVT256500001.0002e − 041.8859e − 04D-SVT191407931.9714e − 043.2171e − 048,000600.07SVT266467171.9926e − 043.2572e − 04ASVT259475581.3320e − 042.0045e − 04M-ASVT251488001.0223e − 041.8879e − 04D-SVT189373241.9591e − 043.1842e − 048,0001000.12SVT258482301.9750e − 043.1624e − 04ASVT254478891.2220e − 042.1145e − 04M-ASVT250475561.0023e − 041.9987e − 04D-SVT183385341.9695e − 043.1436e − 048,0001500.19SVT250437581.9707e − 043.0923e − 04ASVT248436651.3365e − 042.1104e − 04M-ASVT245436661.1102e − 041.9965e − 04D-SVT177350291.9794e − 043.1001e − 0410,0002000.20SVT247858401.9976e − 043.1183e − 04ASVT241856621.2003e − 042.0014e − 04M-ASVT238854411.0041e − 041.9941e − 04D-SVT176696741.9795e − 043.0853e − 0410,0005000.49SVT215716561.9760e − 042.81173e − 04ASVT211712211.2258e − 042.0041e − 04M-ASVT207712341.0005e − 041.9595e − 04D-SVT155592641.9531e − 042.7785e − 0412,0003000.25SVT2421396501.9701e − 043.0300e − 04ASVT2391396661.2254e − 042.3314e − 04M-ASVT2341395561.0005e − 042.0101e − 04D-SVT1731286501.9664e − 043.0193e − 0412,0008000.64SVT1951107501.9964e − 042.6726e − 04ASVT1911155441.2023e − 041.8856e − 04M-ASVT1871155311.0006e − 041.5654e − 04D-SVT141975471.9785e − 042.6492e − 04Table 5
Computational results for large-size problems whenτ=4n.
UnknownMComputational resultsSize (n)Rank (r)pAlgorithmITTime (s)Error 1Error 25,000400.08SVT2199835.91.9870e − 043.2720e − 04ASVT2159755.21.4451e − 042.5656e − 04M-ASVT2099741.31.0907e − 042.1036e − 04D-SVT1568041.41.9393e − 043.1676e − 045,000500.10SVT2169453.71.9655e − 043.2005e − 04ASVT2119431.21.2001e − 042.5543e − 04M-ASVT2069388.21.1007e − 042.1016e − 04D-SVT1527509.21.9991e − 042.2336e − 045,000600.12SVT2139383.41.9786e − 043.1958e − 04ASVT2099321.01.3357e − 042.5151e − 04M-ASVT2019289.11.1110e − 042.1910e − 04D-SVT1517576.31.9481e − 043.1298e − 048,000500.06SVT220392801.9652e − 043.2339e − 04ASVT218389231.5001e − 042.4410e − 04M-ASVT211380091.0944e − 042.1106e − 04D-SVT156319151.9525e − 043.1915e − 048,000600.07SVT217382361.9566e − 043.1953e − 04ASVT214380011.2238e − 042.3131e − 04M-ASVT208379961.1010e − 042.0045e − 04D-SVT153306191.9923e − 043.2345e − 048,0001000.12SVT209377451.9771e − 043.1676e − 04ASVT206375121.2325e − 042.0109e − 04M-ASVT200370081.0056e − 041.9221e − 04D-SVT148305371.9913e − 043.1791e − 048,0001500.19SVT203374141.9488e − 043.0607e − 04ASVT199370021.1125e − 042.0087e − 04M-ASVT196369121.0023e − 041.8989e − 04D-SVT144295071.9832e − 043.1065e − 0410,0002000.20SVT201671351.9474e − 043.0422e − 04ASVT198688521.2365e − 042.5620e − 04M-ASVT195695921.0101e − 041.9962e − 04D-SVT144560151.9315e − 043.0102e − 0410,0005000.49SVT174584531.9652e − 042.7972e − 04ASVT171600331.2020e − 041.9963e − 04M-ASVT167601141.0023e − 041.5651e − 04D-SVT126487581.9709e − 042.8051e − 0412,0003000.25SVT196112841.9603e − 043.0148e − 04ASVT----M-ASVT----D-SVT131103751.9734e − 043.0320e − 0412,0008000.64SVT158884781.9661e − 042.6335e − 04ASVT----M-ASVT----D-SVT115780691.9509e − 042.6139e − 04Note. The mark “-” indicates that the iteration is failing.Table 6
Computational results for large-size problems whenτ=3n.
UnknownMComputational resultsSize (n)Rank (r)pAlgorithmITTime (s)Error 1Error 25,000400.0797SVT1697838.01.9546e − 043.2133e − 04ASVT1617775.11.2230e − 042.3232e − 04M-ASVT1567701.21.0023e − 042.0045e − 04D-SVT1186406.51.9422e − 043.1763e − 045,000500.0995SVT1667343.01.9364e − 043.1582e − 04ASVT1607265.21.2325e − 042.4789e − 04M-ASVT1557189.21.0089e − 042.1004e − 04D-SVT1165780.41.9280e − 043.1234e − 045,000600.1193SVT1647485.61.9450e − 043.1432e − 04ASVT1607401.21.5002e − 042.3004e − 04M-ASVT1547356.31.0980e − 042.0152e − 04D-SVT1155833.11.9562e − 043.1424e − 048,000500.0623SVT168317741.9968e − 043.2825e − 04ASVT165325891.2223e − 042.0058e − 04M-ASVT160324411.0041e − 041.8856e − 04D-SVT118245111.9267e − 043.1490e − 048,000600.0747SVT166293781.9945e − 043.2418e − 04ASVT161296541.2412e − 042.0306e − 04M-ASVT157300011.0002e − 041.5859e − 04D-SVT117237911.9287e − 043.1360e − 048,0001000.1242SVT160303151.9888e − 043.1854e − 04ASVT156312561.2004e − 042.1113e − 04M-ASVT149330001.0100e − 041.8588e − 04D-SVT115238631.9124e − 043.0560e − 048,0001500.1857SVT155272041.9643e − 043.0842e − 04ASVT150286931.2203e − 042.3334e − 04M-ASVT144290031.0045e − 04201414e − 04D-SVT112220021.9250e − 043.0152e − 0410,0002000.1980SVT154526581.9363e − 043.0252e − 04ASVT153533211.1414e − 042.3006e − 04M-ASVT150536621.0051e − 042.0001e − 04D-SVT111446801.9978e − 043.1153e − 0410,0005000.1980SVT133447181.9555e − 042.7855e − 04ASVT131455121.3224e − 042.5101e − 04M-ASVT126455101.0021e − 041.5880e − 04D-SVT98386551.9057e − 042.7139e − 0412,0003000.2469SVT150861101.9587e − 043.0132e − 04ASVT----M-ASVT----D-SVT109819021.9999e − 043.0734e − 0412,0008000.6444SVT121689061.9236e − 042.5786e − 04ASVT----M-ASVT----D-SVT89635171.9120e − 042.5640e − 04Note. The mark “-”indicates that the iteration is failing.In order to show convergence behave of the algorithms briefly, convergence curves of several algorithms are clearly given, which are shown in Figure1 for the different parameters. It is easy to see that our algorithm takes much less computational cost from iteration steps and computing time. That is to say, the D-SVT algorithm is more efficient than the other algorithms especially when the size of matrix M is large.Figure 1
Convergence curves of several algorithms for the different parameters. (a) The iteration steps of several algorithms fort = 5 n. (b) The time of several algorithms for t = 5 n. (c) The iteration steps of several algorithms for t = 4 n. (d) The time of several algorithms for t = 4 n. (e) The iteration steps of several algorithms for t = 3 n. (f) The time of several algorithms for t = 3 n.
(a)(b)(c)(d)(e)(f)


## 5. Concluding Remarks

In this paper, we focus on the problem of completing a low-rank matrix from a small subset of its entries. This model can characterize many applications arising from the areas of signal and image processing, statistical inference, and machine learning. We have proposed a modification of the SVT algorithm for solving the low-rank matrix sparse model. The key step of the algorithm is to update each iteration matrix by a weighting diagonal matrix, without the extra cost. The weighting matrixW was determined adaptively in iteration process. This algorithm is easy to implement and surprisingly effective both in terms of computational cost and storage requirement. Consequently, the matrix would be completed well.



---

*Source: 8812701-2020-12-24.xml*