# Guarantees of Fast Band Restricted Thresholding Algorithm for Low-Rank Matrix Recovery Problem

Authors: Fujun Zhao; Jigen Peng; Kai Sun; Angang Cui
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Affine matrix rank minimization problem is a famous problem with a wide range of application backgrounds. This problem is a combinatorial problem and deemed to be NP-hard. In this paper, we propose a family of fast band restricted thresholding (FBRT) algorithms for low rank matrix recovery from a small number of linear measurements. Characterized via restricted isometry constant, we elaborate the theoretical guarantees in both noise-free and noisy cases. Two thresholding operators are discussed and numerical demonstrations show that FBRT algorithms have better performances than some state-of-the-art methods. Particularly, the running time of FBRT algorithms is much faster than the commonly singular value thresholding algorithms.


---

## Body

## 1. Introduction

The affine matrix rank minimization (AMRM) problem, which is to recover a low-rank matrix from only a small number of linear measurements, can be described as the following optimization problem:(1)minX∈ℂn1×n2rankXs.t.AX−b2≤η,where A∈ℒℂn1×n2,ℂd is a given linear map, b∈ℂd is a given vector, and η≥0 is error tolerance. This problem has got much attention in recent years and many applications arising in various areas can be captured by solving model (1), for example, matrix completion [1, 2], background modeling [3], subspace clustering [4], phase retrieval [5, 6], image inpainting [7], and other applications [8, 9]. The lines and the symbols in all figures are too small to see. It is better to enlarge them. Unfortunately, ARMR problem is known to be NP-hard. Therefore, without further assumptions on A and X, solving this problem would be computationally intractable. To overcome this shortcoming, many researchers have focused on replacing rankX with other penalties GX, such as Schatten p-norm 0<p<1 [10], Minimax Concave Plus (MCP) [11], Smoothly Clipped Absolute Deviation (SCAD) [12], Logarithm [13], Geman [14], and Laplace [15], and considered the following optimization problem:(2)minX∈ℂn1×n2GXs.t.AX−b2≤η,or the corresponding unconstrained optimization problem:(3)minX∈ℂn1×n212AX−b22+λ⋅GX,where λ>0 is a regularization parameter. Model (3) can be transformed into a fixed point problem described as(4)X=ℋX−s⋅A∗AX−b,where A∗ is the dual operator of A, ℋ is the thresholding operator, and s is a step size parameter. Naturally, we have corresponding iterative thresholding algorithm. Given a fixed penalty G⋅, there have been many theoretical guarantees. However, there are still some challenges as follows:(I)
Most of convergence results were developed for model (3) with fixed λ, and it is difficult to choose an appropriate parameter λ(II)
It is hard to design the thresholding operatorℋ⋅ for penalties GX except some special penalties, such as Schatten p-norm p=0,1,1/2,2/3 [2, 16–18] and SCAD [12](III)
Every iteration of the iterative thresholding algorithms needs to calculate the SVD, and if the size of the original matrix is large, the iterative thresholding algorithms will be time consumingTwo papers that relate to our work need to be overviewed here. Chartrand [19] firstly studied the way to compute the penalty G⋅ via a given thresholding operator. However, his work did not show the stability guarantees of thresholding algorithms. Wei et al. [20] proposed an iterative hard algorithm with subspace projections, which had relatively lower computation complexity. However, his work did not examine the performance in the noisy case. Taking into account these work, we try to design a new algorithm and overcome these shortcomings to a certain extent.In this paper, we design a family of new fast band restricted thresholding (FBRT) algorithms to solve model (1) and elaborate the theoretical guarantees in both noise-free and noisy cases. In fact, many related works [17, 18, 21, 22] focus on the stability of the optimal solution of the model. For the effect of noise on the algorithm, an empirical explanation is often given through numerical experiments. At the end of this paper, we give some simple examples to roughly verify our theoretical results.The remainder of this paper is organized in the following. In Section2, we introduce some basic preliminary results and notations. In Section 3, we describe the fast band restricted thresholding (FBRT) algorithm. In Section 4, we prove the convergence of the FBRT algorithm. In Section 5, we display the numerical simulations, and then conclude this paper in Section 6. All the proofs are presented in Appendix.


## 2. Preliminaries

In this section, we introduce some notations and useful results to facilitate the following research.


### 2.1. Notations

We denoteA as a linear operator from ℂn1×n2 to ℂd. For any X∈ℂn1×n2, AX is X,AiFi=1d, where X,AiF=trXAi∗ is a Frobenius inner product. Thus, we naturally obtain the dual operator A∗ as follows:(5)A∗:ℂd⟶ℂn1×n2b↦∑i=1dbiAi.We also denoteX¯ as the original matrix with rankX¯=r and e=b−AX¯ as the noise with error tolerance η=e2. For any subspaces Ω1,Ω2⊂ℂn1×n2, we obtain the sum of subspaces Ω1+Ω2, and we also rewrite Ω1∩Ω2⊥ as Ω1\Ω2.


### 2.2. Some Useful Results

In this section, we introduce some useful results, which show the relationship between the original low-rank matrix and the solution of model (1). For this purpose, we review the definition of RIC, which plays an important role in the following research.Definition 1.
(see [23]). Given a linear operator A:ℂn1×n2⟶ℂd and 1≤r≤minm,n, the restricted isometry constant δr is the smallest nonnegative number, such that, for any matrix X∈ℂn1×n2, with rankX≤r, we have the following inequality:(6)1−δrXF2≤AX22≤1+δrXF2,where ⋅F is the Frobenius norm.
For a given linear mapA, it is difficult to calculate the restricted isometry constant δr, but for Gaussian random linear map, there has been a result that the number of measurements d≥c0rn1+n2logn1n2 (c0 only depends on δ) is sufficient to yield an RIC of δ with high probability [23].
In the noisy case, the following theorem claims that the solution of model (1) cannot be far of from the original low-rank matrix, if A satisfies a certain RIC. The related theorem about compressive sensing is mentioned in [24], see equation (5.24).Theorem 1.
LetZ,Zη be two solution of (1) within error tolerance η (i.e., AZ−b2,AZη−b2≤η). If rankZ=rankZη=r and δ2r<1, we can obtain a stability claim of the form(7)Z−Zη22<4η21−δ2r.If we takeη=0 in Theorem 1, we obtain the following uniqueness result, in a noise-free case.Corollary 1.
LetZ be a r-rank solution of AX=b. If A satisfies(8)δ2r<1,then Z is the unique lowest rank solution.Taking into account the abovementioned results, it implies that the original low-rank matrixX¯ is the solution of model (1), if A satisfies a certain RIC.


## 2.1. Notations

We denoteA as a linear operator from ℂn1×n2 to ℂd. For any X∈ℂn1×n2, AX is X,AiFi=1d, where X,AiF=trXAi∗ is a Frobenius inner product. Thus, we naturally obtain the dual operator A∗ as follows:(5)A∗:ℂd⟶ℂn1×n2b↦∑i=1dbiAi.We also denoteX¯ as the original matrix with rankX¯=r and e=b−AX¯ as the noise with error tolerance η=e2. For any subspaces Ω1,Ω2⊂ℂn1×n2, we obtain the sum of subspaces Ω1+Ω2, and we also rewrite Ω1∩Ω2⊥ as Ω1\Ω2.


## 2.2. Some Useful Results

In this section, we introduce some useful results, which show the relationship between the original low-rank matrix and the solution of model (1). For this purpose, we review the definition of RIC, which plays an important role in the following research.Definition 1.
(see [23]). Given a linear operator A:ℂn1×n2⟶ℂd and 1≤r≤minm,n, the restricted isometry constant δr is the smallest nonnegative number, such that, for any matrix X∈ℂn1×n2, with rankX≤r, we have the following inequality:(6)1−δrXF2≤AX22≤1+δrXF2,where ⋅F is the Frobenius norm.
For a given linear mapA, it is difficult to calculate the restricted isometry constant δr, but for Gaussian random linear map, there has been a result that the number of measurements d≥c0rn1+n2logn1n2 (c0 only depends on δ) is sufficient to yield an RIC of δ with high probability [23].
In the noisy case, the following theorem claims that the solution of model (1) cannot be far of from the original low-rank matrix, if A satisfies a certain RIC. The related theorem about compressive sensing is mentioned in [24], see equation (5.24).Theorem 1.
LetZ,Zη be two solution of (1) within error tolerance η (i.e., AZ−b2,AZη−b2≤η). If rankZ=rankZη=r and δ2r<1, we can obtain a stability claim of the form(7)Z−Zη22<4η21−δ2r.If we takeη=0 in Theorem 1, we obtain the following uniqueness result, in a noise-free case.Corollary 1.
LetZ be a r-rank solution of AX=b. If A satisfies(8)δ2r<1,then Z is the unique lowest rank solution.Taking into account the abovementioned results, it implies that the original low-rank matrixX¯ is the solution of model (1), if A satisfies a certain RIC.


## 3. Fast Band Restricted Thresholding Algorithm

In this section, we will design a new fast band restricted thresholding (FBRT) algorithm. For this purpose, we need to review some thresholding algorithms for (1) in previous work and compare FBRT algorithm with other algorithms.Similar to compressive sensing problem, both iterative hard thresholding and iterative soft thresholding, also known as SVP [16] and SVT [2], are simple and efficient algorithms for low-rank matrix recovery. In pursuit of better results, some alternative algorithms, such as HFPA [22], thresholding function for Schatten 2/3-norm [18], SCAD [12], and firm thresholding [25], have been proposed. We present these commonly used thresholding functions in Figure 1, and it is obvious that all of them satisfy the following definition.Figure 1
Typical thresholding functionhτ⋅ with τ=1.Definition 2.
A functionhτ of ℝ+ with parameter τ>0 is called as band restricted thresholding (BRT) function, if it satisfies(I)
hτu=0, with u≤τ(II)
hτu≤hτv, with τ<u≤v(III)
There exists a constantc∈0,1 (band parameter), such that u−cτ≤hτu≤u, with u≥τ
According to Definition2, the following Table 1 shows the corresponding band parameter c of these BRT functions.
Given a BRT functionhτ, we can obtain a thresholding operator ℋτ⋅ which is defined as(9)ℋτX=∑i=1hτσiuivi∗,where ∑i=1σiuivi∗ is the SVD of X, and we can also have the corresponding thresholding algorithm described as(10)Wk=Xk−1+A∗b−AXk−1,Xk=ℋτWk,where τ is the threshold parameter. In fact, every iteration of the abovementioned algorithm needs to compute the SVD of Wk. Thus, if N=n1+n2 is large, this algorithm will be computationally expensive. To improve the efficiency of algorithm, we propose to orthogonally project Wk onto a subspace Sk, which was first applied in [20]. Sk, which is the tangent space of the rank r matrix manifold at Xk, is described as(11)Sk≔UkP+QVk∗:P∈ℂr×n2,Q∈ℂn1×r,where Uk∈ℂn1×r and Vk∈ℂr×n2 are the left and right singular vectors of Xk. Furthermore, for any matrix Z∈ℂn1×n2, PSkZ is defined as(12)PSkZ=UkUk∗Z+ZVkVk∗−UkUk∗ZVkVk∗=I−UkUk∗ZI−VkVk∗.
Meanwhile, we derive the fast band restricted thresholding (FBRT) algorithm described as in Algorithm1.Table 1
Band parameterc for different thresholding functions.
h
τ
,
∗
h
τ
,
0
h
τ
,
1
h
τ
,
1
/
2
h
τ
,
2
/
3
h
τ
,
SCAD
h
τ
,
firm
c
0
1
1
/
3
3
/
4
1
1Algorithm 1: Fast band restricted thresholding (FBRT).
Input: A∈ℒℂn1×n2,ℂd, r∈ℕ+, b∈ℂd, and error tolerance ε≥0
Initialization: k=0,X0=ℋσr+10W0, where W0=A∗b and σr+1k is the r+1-th singular value of W0.
Repeat:
(1)
k
⟵
k
+
1,
(2)
W
k
=
X
k
−
1
+
P
S
k
−
1
A
∗
b
−
A
X
k
−
1,
(3)
W
k
=
U
k
Σ
k
V
k
∗, based on the singular value decomposition,
(4)
X
k
=
U
k
H
σ
r
+
1
k
Σ
k
V
k
∗, where σr+1k is the r+1-th singular value of the matrix Wk.
Until: the matrix Xk¯, with AXk¯−b2≤ε.Remark 1.
The threshold parameterτ plays an important role which affects the performance of FBRT algorithm. Here, we let τ=σr+1k, and we will show the theoretical performance of FBRT algorithm in the following discussion.Remark 2.
The stopping criterion isAXk¯−b2≤ε. Taking into account Theorem 1, Xk¯ cannot be far of from X¯, if A satisfies a certain RIC. On the contrary, it is an important situation of classified discussion that Xn is close to X¯, and the detail will be shown in the following section.
It is worth noting thatXk+A∗b−AXk is always a full rank matrix and computing the SVD will use ON3 N=m+n floating point operations flops. In the mean time, Wk in every iteration of FBRT algorithm is a 2r-rank matrix, and according to the QR factorization, we can obtain that(13)Wk=QR=QR1∗Q1∗,where Wk=QR and R∗=Q1R1 are the QR factorizations of Wk and R∗, with Q∈ℂn1×2r,R∈ℂ2r×n2,R1∈ℂ2r×2r, and Q1∈ℂn2×2r. Thus, the SVD of Wk can be obtained from the SVD of R1, and computing the SVD of Wk, will use Or3 floating point operations instead of ON3 flops [20].


## 4. Analysis of the FBRT Algorithm

In this section, we will study theoretically the performance of the FBRT algorithm, and the following Theorem2 and 3 show the theoretical guarantees in both noise-free and noisy cases.Theorem 2.
Let the sequenceXn be defined by the FBRT algorithm with AX=AX¯=b and rankX¯=r. If the thresholding operator in the FBRT algorithm is the BRT operator with a band parameter c and the following constant(14)ρ≔4+2c2rδ2r+δ3r+4+2c2rδ2r+1σminX¯X¯F,is less than 1, we have(15)Xn−X¯F≤ρnX0−X¯F.Particularly,ρ<1 can be satisfied if(16)δ3r≤124+2c2r+4+2c2rrσmaxX¯/σminX¯.The proof of Theorem2 is given in Appendix, and we discuss condition of Theorem 2, which shows the performance of the FBRT algorithm in the AMRM problem.Remark 3.
According to Theorem2, the performance of the FBRT algorithm depends on σmaxX¯/σminX¯, i.e., the condition number of the original r-rank matrix X¯. It plays an important role for the projection operator PSn.
In the noisy case, the error toleranceη is a significant parameter. According to Theorem 1, we know that there exists a gap between the solution of model (1) and the original low-rank matrix. Thus, we always assume that the model error is small.Theorem 3.
Assume thatX¯F≥μη, where rankX¯=r and η=e2 is error tolerance. Let the sequence Xn be defined by the FBRT algorithm with AX−b2≤η. If the thresholding operator in the FBRT algorithm is the BRT operator with a band parameter c and A satisfies(17)δ3r≤μ24+2c2rμ+11+4+2c2r/σminX¯X¯F−μη,then the sequence Xn must satisfy one of the following result:(i)
There exists a positive integern, such that(18)Xn−X¯F≤c′η,wherec′=4μ+12+c2r.(ii)
For any positive integern, we have(19)Xn−X¯F≤ρnX0−X¯F+4+2c2r1+δ2r+11−ρη,whereρ=μ/μ+1<1.The proof of this theorem is also presented in Appendix. First of all, ifδ3r satisfies the condition of Theorem 3, δ3r≤μ/μ+1<1. Besides, when the error tolerance η is not too large, the result of Theorem 3 illustrates that there exists a positive integer n, such that Xn will be close to the original matrix X¯. Since A is a bounded linear operator, it implies that AXn is close to AX¯. In the mean time, the fact that AXn is close to AX¯ also implies that Xn is close to the original matrix X¯, according to Theorem 1. On the contrary, the parameter μ in this theorem is a key parameter, and performance of algorithm will get better as X¯F−μη is close to 0. Meanwhile, the performance of algorithm also depends on the condition number of the original r-rank matrix X¯, which is similar to Theorem 2.


## 5. Numerical Demonstration

In this section, we present some empirical observations of FBRT algorithms with two thresholding operator:(20)hτ,atanu=u−τ+2τπarctanu−τ,ifu≥τ,0,ifu<τ,Atan,hτ,firmu=u,ifu>a⋅τ,aa−1x−u,ifτ≤u≤a⋅τ,firm,0,ifu<τ,and compare them with some state-of-the-art methods (singular value thresholding (SVT) algorithm [2], singular value pursuit (SVP) algorithm [16], half norm fixed point (Half) algorithm [22], and Riemannian gradient descent (RGrad) algorithm [20]).Here, we define two quantities to quantify performance of the algorithm:SR≔d/n1n2, i.e., the number of measurements divided by the number of entries of the matrix, which denotes the sampling ratio, andOS≔d/rn1+n2−r is the oversampling ratio, i.e., the ratio between the number of sampled entries and the “true dimensionality” of an n1×n2 matrix of rank r. In fact, if OS <1, we cannot recover the original low-rank matrix because there are always an infinite number of matrices of rank r with the given entries [26]. We use the relative error (RE) in the Frobenius norm(21)RE≔M−XoptFMF,to evaluate the closeness of Xopt to M, where Xopt is the “optimal” solution of the algorithm and M is the original low-rank matrix.


### 5.1. Empirical Phase Transition

In this section, we test how many measurements are needed to recover a low rank matrix. For the sake of simplicity, we setn=m and generate rank r matrix X=LR, where L∈ℝn×r and R∈ℝr×n and the components of L and R is sampled from the standard normal distribution. The stopping criterion is as follows:(22)Xk−Xk−1FXk−1F≤10−8.Simulations of FBRT algorithms are repeated for 10 times, and numerical results are reported in Table2. We consider an algorithm to successfully recover the low rank matrix X if the “optimal” solution of this algorithm with RE≤0.01. Furthermore, we denote rmin as the largest rank such that the corresponding max RE≤0.01 and rmax as the smallest rank such that the corresponding min RE≥0.01. OSmax is computed via rmin, and OSmin is computed via rmax. Figure 2 shows the empirical of the tested algorithms on the (SR and OS), where we calculate oversampling ratio OS via r=rmin+rmax/2.Table 2
Numerical results of two FBRT algorithms: FBRT-Atan and FBRT-firm (a = 3) with fixed m=n=300. For any SR, the maximum of 10 relative errors is less than 0.01 when r≤rmin and the minimum of 10 relative errors is greater than or equal to 0.01 when r>rmax.
z
FBRT-Atan
FBRT-firm
SR
Min RE
Max RE
Min RE
Max RE
0.1
r
min
=
11
1.0260e − 5
0.0023
r
min
=
11
2.1594e − 5
0.0068
r
max
=
13
0.0079
0.6592
r
max
=
12
2.7247e − 4
0.5478
0.2
r
min
=
26
6.1794e − 6
6.5852e − 5
r
min
=
27
8.8405e − 6
2.2534e − 4
r
max
=
28
3.3154e − 4
0.5499
r
max
=
28
3.6679e − 4
0.5143
0.3
r
min
=
43
7.6326e − 6
9.6796e − 6
r
min
=
44
8.2757e − 5
3.0298e − 4
r
max
=
45
0.0017
0.5188
r
max
=
45
0.0032
0.4816
0.4
r
min
=
61
7.7705e − 6
1.8222e − 5
r
min
=
61
7.8113e − 6
8.3863e − 6
r
max
=
62
6.8547e − 5
0.4236
r
max
=
63
0.0011
0.4392
0.5
r
min
=
80
7.0491e − 6
7.3872e − 6
r
min
=
81
1.1833e − 5
2.2862e − 5
r
max
=
81
1.1140e − 5
0.3924
r
max
=
83
0.0059
0.3871
0.6
r
min
=
102
7.4470e − 6
2.3292e − 5
r
min
=
103
1.9080e − 5
6.4072e − 5
r
max
=
103
2.2913e − 5
0.3510
r
max
=
105
0.0016
0.3472
0.7
r
min
=
127
7.7453e − 6
5.2701e − 5
r
min
=
128
1.8729e − 5
1.3984e − 4
r
max
=
128
5.1908e − 5
0.2978
r
max
=
129
1.5370e − 4
0.2578
0.8
r
min
=
156
6.7983e − 6
7.4203e − 6
r
min
=
158
5.5031e − 5
2.1316e − 4
r
max
=
158
1.3876e − 4
0.2559
r
max
=
159
3.2228e − 4
0.2214
0.9
r
min
=
196
9.9473e − 6
4.7502e − 4
r
min
=
197
4.6863e − 5
1.7010e − 4
r
max
=
197
2.5510e − 4
0.1592
r
max
=
198
0.0011
0.1610Figure 2
Empirical phase transition curves for FBRT algorithms: FBRT-Atan and FBRT-firm (a = 3) with fixed m=n=300Table2 and Figure 2 show that these two FBRT algorithms can affect recover rank r matrices, where OS is close to 1, and there is not much difference between two empirical phase transition curves.


### 5.2. Comparison with the State-of-the-Art Algorithms in Noise-Free Case

In this section, we consider the noise-free case and test the performances of FBRT algorithms on matrix completion problems. We also generate a low rank matrix in the way ofSection 5.1. The stopping criterion is as follows:(23)Xk−Xk−1FXk−1F≤10−8.Simulations are repeated for 10 times, and numerical results are reported in Tables3 and 4 and Figure 3.Table 3
Numerical results of matrix recovery algorithms: SVT, SVP, Half, FBRT-Atan, and FBRT-firm (a = 3) with different n but fixed rank=300 and OS=2.
SVT
SVP
Half
FBRT-Atan
FBRT-firm
n = 400r = 50OS = 2
taver
12.45
6.88
12.42
5.00
5.04
REaver
0.20
1.76e − 7
1.61e − 4
1.76e − 7
1.77e − 7
tmax
13.47
7.07
13.32
5.15
5.27
tmin
11.61
6.72
7.21
4.88
4.94
REmax
0.21
1.92e − 7
1.65e − 4
1.85e − 7
1.87e − 7
REmin
0.19
1.70e − 7
1.57e − 4
1.69e − 7
1.68e − 7
n = 1000r = 50OS = 2
taver
131.52
172.59
420.00
92.75
93.00
REaver
0.44
5.37e − 7
1.20e − 4
5.54e − 7
5.48e − 7
tmax
139.66
174.62
443.33
93.81
94.78
tmin
122.04
170.64
379.53
91.22
91.62
REmax
0.45
5.48e − 7
1.21e − 4
5.92e − 7
5.73e − 7
REmin
0.41
5.33e − 7
1.18e − 4
5.32e − 7
5.36e − 7Table 4
Numerical results of matrix recovery algorithms: RGrad, FBRT-Atan, and FBRT-firm (a = 3) with different n, rank and OS=2.l
RGrad
FBRT-Atan
FBRT-firm
n = 100r = 19SR = 0.4
Aver. RE
0.0354
5.5880e-6
4.7998e-6
Aver. Time
8.1457
9.3389
8.5035
Max RE
0.3541
8.2501e − 6
6.1506e − 6
Max time
13.1745
11.6156
10.0949
Min RE
4.1929e − 6
4.3110e − 6
3.9417e − 6
Min time
0.5778
7.4130
6.9589
n = 1000r = 50OS = 2
Aver. RE
5.6007e − 7
5.4427e − 7
5.4482e − 7
Aver. Time
99.6237
95.4349
97.2309
Max RE
6.3984e − 7
5.5862e − 7
5.6776e − 7
Max time
103.0736
98.7222
100.1280
Min RE
5.3833e − 7
5.2797e − 7
5.2966e − 7
Min time
98.2743
93.0526
94.3025Figure 3
Convergence curves for matrix recovery algorithms: SVT, SVP, Half, FBRT-Atan and FBRT-firm (a = 3) with different n = 1000, 400 but fixed rank = 50 and OS = 2. (a) n = 1000. (b) n = 400.
(a)
(b)In Table3, we show the comparison experiments with SVT, SVP, and Half. We conduct the tests for n∈400,1000, r=50, and OS=2 and record the average, maximum, and minimum values of relative errors and running time, respectively. Based on Table 3, we can obverse that the relative errors of FBRT algorithms are smaller, and the running time is also faster. In the meantime, the running time of FBRT algorithms increases slowly as n increases. We explore the trends, displayed in Figure 3, between the relative error and the running time of the first time algorithm operation results. In Table 4, we show the comparison experiments with RGrad. We conduct the tests in two cases: n=100,r=19,SR=0.4 and n=1000,r=50,OS=2. Based on Table 4, we see that the running time of different algorithms is about the same, but the relative errors of FBRT algorithms are smaller than the relative error of RGrad. Therefore, we can find that FBRT algorithms perform better than others in noise-free case.


### 5.3. Comparison with the State-of-the-Art Algorithms in Noisy Case

In this section, we consider the noisy case and compare the performances of FBRT algorithms with RGard algorithm on the image inpainting problems. Here, we test these algorithms on the grayscale image:419×400 intracranial venous image (IVI), and we obtain approximated low-rank image truncated from IVI with rank r=35. We generate the noised image with normal distribution by(24)imnoiseimage,“gaussian”,0,σ2,where σ2 is the variance of normal distribution, and generate the sample image from noised image with SR=0.4. We consider the variance σ2∈0.01,0.001 and iterations are 150 and 550, respectively. The original image, its approximated low-rank image, its noised image, and its recovering images of different algorithms and displayed in Figure 4, respectively. Figure 4(a) is original IVI with full rank. Figure 4(b) is a approximated low-rank image truncated from Figure 4(a) with rank r=35. Figure 4(c) is a noised image of Figure 4(b) with σ2=0.01. Figures 4(d)–4(f) are the recovering image via different algorithms, respectively. Numerical results for image inpainting are reported in Table 5. Comparing these comparison experiments, we find that FBRT algorithms perform much better that RGard algorithm in image inpainting noisy case.Figure 4
(a) Original419×400 IVI image with full rank; (b) approximated image of (a) with rank 35; c noised image of (b) with σ2=0.01; (d, e, and f) the recovering images via RGrad, FBRT-Atan, and FBRT-firm, respectively, SR=0.4 (noisy case). (a) Original IVI. (b) Low-rank IVI. (c) IVI with noise. (d) RGrad0.4. (e) FBRT-atan0.4. (f) FBRT-_rm0.4.
(a)
(b)
(c)
(d)
(e)
(f)Table 5
Numerical results of four algorithms on image inpainting (approximated low-rank IVI) with different ranks (noisy case).
RE
RGrad
FBRT-Atan
FBRT-firm
σ
2
=
0.01
0.4577 (156)
0.4108 (114)
0.4017 (121)
σ
2
=
0.001
0.1262 (524)
0.1251 (514)
0.1250 (578)


## 5.1. Empirical Phase Transition

In this section, we test how many measurements are needed to recover a low rank matrix. For the sake of simplicity, we setn=m and generate rank r matrix X=LR, where L∈ℝn×r and R∈ℝr×n and the components of L and R is sampled from the standard normal distribution. The stopping criterion is as follows:(22)Xk−Xk−1FXk−1F≤10−8.Simulations of FBRT algorithms are repeated for 10 times, and numerical results are reported in Table2. We consider an algorithm to successfully recover the low rank matrix X if the “optimal” solution of this algorithm with RE≤0.01. Furthermore, we denote rmin as the largest rank such that the corresponding max RE≤0.01 and rmax as the smallest rank such that the corresponding min RE≥0.01. OSmax is computed via rmin, and OSmin is computed via rmax. Figure 2 shows the empirical of the tested algorithms on the (SR and OS), where we calculate oversampling ratio OS via r=rmin+rmax/2.Table 2
Numerical results of two FBRT algorithms: FBRT-Atan and FBRT-firm (a = 3) with fixed m=n=300. For any SR, the maximum of 10 relative errors is less than 0.01 when r≤rmin and the minimum of 10 relative errors is greater than or equal to 0.01 when r>rmax.
z
FBRT-Atan
FBRT-firm
SR
Min RE
Max RE
Min RE
Max RE
0.1
r
min
=
11
1.0260e − 5
0.0023
r
min
=
11
2.1594e − 5
0.0068
r
max
=
13
0.0079
0.6592
r
max
=
12
2.7247e − 4
0.5478
0.2
r
min
=
26
6.1794e − 6
6.5852e − 5
r
min
=
27
8.8405e − 6
2.2534e − 4
r
max
=
28
3.3154e − 4
0.5499
r
max
=
28
3.6679e − 4
0.5143
0.3
r
min
=
43
7.6326e − 6
9.6796e − 6
r
min
=
44
8.2757e − 5
3.0298e − 4
r
max
=
45
0.0017
0.5188
r
max
=
45
0.0032
0.4816
0.4
r
min
=
61
7.7705e − 6
1.8222e − 5
r
min
=
61
7.8113e − 6
8.3863e − 6
r
max
=
62
6.8547e − 5
0.4236
r
max
=
63
0.0011
0.4392
0.5
r
min
=
80
7.0491e − 6
7.3872e − 6
r
min
=
81
1.1833e − 5
2.2862e − 5
r
max
=
81
1.1140e − 5
0.3924
r
max
=
83
0.0059
0.3871
0.6
r
min
=
102
7.4470e − 6
2.3292e − 5
r
min
=
103
1.9080e − 5
6.4072e − 5
r
max
=
103
2.2913e − 5
0.3510
r
max
=
105
0.0016
0.3472
0.7
r
min
=
127
7.7453e − 6
5.2701e − 5
r
min
=
128
1.8729e − 5
1.3984e − 4
r
max
=
128
5.1908e − 5
0.2978
r
max
=
129
1.5370e − 4
0.2578
0.8
r
min
=
156
6.7983e − 6
7.4203e − 6
r
min
=
158
5.5031e − 5
2.1316e − 4
r
max
=
158
1.3876e − 4
0.2559
r
max
=
159
3.2228e − 4
0.2214
0.9
r
min
=
196
9.9473e − 6
4.7502e − 4
r
min
=
197
4.6863e − 5
1.7010e − 4
r
max
=
197
2.5510e − 4
0.1592
r
max
=
198
0.0011
0.1610Figure 2
Empirical phase transition curves for FBRT algorithms: FBRT-Atan and FBRT-firm (a = 3) with fixed m=n=300Table2 and Figure 2 show that these two FBRT algorithms can affect recover rank r matrices, where OS is close to 1, and there is not much difference between two empirical phase transition curves.


## 5.2. Comparison with the State-of-the-Art Algorithms in Noise-Free Case

In this section, we consider the noise-free case and test the performances of FBRT algorithms on matrix completion problems. We also generate a low rank matrix in the way ofSection 5.1. The stopping criterion is as follows:(23)Xk−Xk−1FXk−1F≤10−8.Simulations are repeated for 10 times, and numerical results are reported in Tables3 and 4 and Figure 3.Table 3
Numerical results of matrix recovery algorithms: SVT, SVP, Half, FBRT-Atan, and FBRT-firm (a = 3) with different n but fixed rank=300 and OS=2.
SVT
SVP
Half
FBRT-Atan
FBRT-firm
n = 400r = 50OS = 2
taver
12.45
6.88
12.42
5.00
5.04
REaver
0.20
1.76e − 7
1.61e − 4
1.76e − 7
1.77e − 7
tmax
13.47
7.07
13.32
5.15
5.27
tmin
11.61
6.72
7.21
4.88
4.94
REmax
0.21
1.92e − 7
1.65e − 4
1.85e − 7
1.87e − 7
REmin
0.19
1.70e − 7
1.57e − 4
1.69e − 7
1.68e − 7
n = 1000r = 50OS = 2
taver
131.52
172.59
420.00
92.75
93.00
REaver
0.44
5.37e − 7
1.20e − 4
5.54e − 7
5.48e − 7
tmax
139.66
174.62
443.33
93.81
94.78
tmin
122.04
170.64
379.53
91.22
91.62
REmax
0.45
5.48e − 7
1.21e − 4
5.92e − 7
5.73e − 7
REmin
0.41
5.33e − 7
1.18e − 4
5.32e − 7
5.36e − 7Table 4
Numerical results of matrix recovery algorithms: RGrad, FBRT-Atan, and FBRT-firm (a = 3) with different n, rank and OS=2.l
RGrad
FBRT-Atan
FBRT-firm
n = 100r = 19SR = 0.4
Aver. RE
0.0354
5.5880e-6
4.7998e-6
Aver. Time
8.1457
9.3389
8.5035
Max RE
0.3541
8.2501e − 6
6.1506e − 6
Max time
13.1745
11.6156
10.0949
Min RE
4.1929e − 6
4.3110e − 6
3.9417e − 6
Min time
0.5778
7.4130
6.9589
n = 1000r = 50OS = 2
Aver. RE
5.6007e − 7
5.4427e − 7
5.4482e − 7
Aver. Time
99.6237
95.4349
97.2309
Max RE
6.3984e − 7
5.5862e − 7
5.6776e − 7
Max time
103.0736
98.7222
100.1280
Min RE
5.3833e − 7
5.2797e − 7
5.2966e − 7
Min time
98.2743
93.0526
94.3025Figure 3
Convergence curves for matrix recovery algorithms: SVT, SVP, Half, FBRT-Atan and FBRT-firm (a = 3) with different n = 1000, 400 but fixed rank = 50 and OS = 2. (a) n = 1000. (b) n = 400.
(a)
(b)In Table3, we show the comparison experiments with SVT, SVP, and Half. We conduct the tests for n∈400,1000, r=50, and OS=2 and record the average, maximum, and minimum values of relative errors and running time, respectively. Based on Table 3, we can obverse that the relative errors of FBRT algorithms are smaller, and the running time is also faster. In the meantime, the running time of FBRT algorithms increases slowly as n increases. We explore the trends, displayed in Figure 3, between the relative error and the running time of the first time algorithm operation results. In Table 4, we show the comparison experiments with RGrad. We conduct the tests in two cases: n=100,r=19,SR=0.4 and n=1000,r=50,OS=2. Based on Table 4, we see that the running time of different algorithms is about the same, but the relative errors of FBRT algorithms are smaller than the relative error of RGrad. Therefore, we can find that FBRT algorithms perform better than others in noise-free case.


## 5.3. Comparison with the State-of-the-Art Algorithms in Noisy Case

In this section, we consider the noisy case and compare the performances of FBRT algorithms with RGard algorithm on the image inpainting problems. Here, we test these algorithms on the grayscale image:419×400 intracranial venous image (IVI), and we obtain approximated low-rank image truncated from IVI with rank r=35. We generate the noised image with normal distribution by(24)imnoiseimage,“gaussian”,0,σ2,where σ2 is the variance of normal distribution, and generate the sample image from noised image with SR=0.4. We consider the variance σ2∈0.01,0.001 and iterations are 150 and 550, respectively. The original image, its approximated low-rank image, its noised image, and its recovering images of different algorithms and displayed in Figure 4, respectively. Figure 4(a) is original IVI with full rank. Figure 4(b) is a approximated low-rank image truncated from Figure 4(a) with rank r=35. Figure 4(c) is a noised image of Figure 4(b) with σ2=0.01. Figures 4(d)–4(f) are the recovering image via different algorithms, respectively. Numerical results for image inpainting are reported in Table 5. Comparing these comparison experiments, we find that FBRT algorithms perform much better that RGard algorithm in image inpainting noisy case.Figure 4
(a) Original419×400 IVI image with full rank; (b) approximated image of (a) with rank 35; c noised image of (b) with σ2=0.01; (d, e, and f) the recovering images via RGrad, FBRT-Atan, and FBRT-firm, respectively, SR=0.4 (noisy case). (a) Original IVI. (b) Low-rank IVI. (c) IVI with noise. (d) RGrad0.4. (e) FBRT-atan0.4. (f) FBRT-_rm0.4.
(a)
(b)
(c)
(d)
(e)
(f)Table 5
Numerical results of four algorithms on image inpainting (approximated low-rank IVI) with different ranks (noisy case).
RE
RGrad
FBRT-Atan
FBRT-firm
σ
2
=
0.01
0.4577 (156)
0.4108 (114)
0.4017 (121)
σ
2
=
0.001
0.1262 (524)
0.1251 (514)
0.1250 (578)


## 6. Conclusions

In this paper, we proposed the FBRT algorithm and developed the theoretical guarantees in both noise-free and noisy case. The numerical demonstration showed that this algorithm is effective. However, it is important to estimate error toleranceη, which has a great influence on FBRT algorithm. In the low SNR cases, more priori assumptions of the original low rank matrix are necessary, and we will study it in our future work. On the contrary, the condition number of the original matrix is also a significant parameter. As we know, phase retrieval [5, 6] and blind deconvolution [27, 28] problems can be transformed into a rank one matrix recovery problem. Since the condition number of a rank one matrix is always equal to one, it may be worth to study phase retrieval and blind deconvolution problems via the FBRT algorithm.



---

*Source: 9578168-2020-04-30.xml*