IEEE Signal Processing - July 2018 - 23

but the computational cost is significantly lower. To obtain ft ) satisfies
accuracy, meaning that the final estimate (Lt , R
t tT-X
LR

F

# f·v r ,

(27)

we only need to run a total of T = O (log (1/f)) iterations
for matrix sensing and T = O (n 0 r log (1/f)) iterations for matrix completion.
We now briefly discuss the overall computational complexity, and, for simplicity, we assume n 1 = n 2 = n. For matrix
sensing, let T0 be the maximum time of multiplying the matrix
A l with a vector of compatible dimension. Each gradient step
(19) can be performed in time O (mrT0 + nr). The complexity
of computing the initial solution is a bit subtler. To this end, we
first note that by standard matrix perturbation bounds, one can
show that the matrix A * ( y) and its singular values are sufficiently close to those of X under the condition of Theorem 3;
in particular, one has A * ( y) - X # c 0 v r / r , and the rth
and (r + 1) th singular values of A * ( y) are at most c 0 v r / r
away from the corresponding singular values of X, where c 0
is a small constant. With such properties of A * ( y), one does
not need to compute the exact singular values/vectors of A * ( y)
to meet the initialization condition (24); rather, it suffices to
find a rank-r approximation of A * ( y) with the property
L0 R 0T - A * ( y) # c 0 v r / r . This can be done using, for
example, the randomized SVD procedure in [45], which takes
O (mrT0 log n + nr 2) time to compute; see [45, Th. 1.2 and eq.
(1.11)] with q = log n. Put together, the overall time complexity
is O (mrT0 log (n/f)) for achieving f-accuracy.
For matrix completion, to obtain the initial solution, we can
again follow similar arguments as mentioned previously to
show that it suffices to compute a rank-r approximation of the
matrix p -1 PX (Y ), which is close to X and has a sufficiently
large spectral gap. Since p -1 PX (Y ) is a sparse matrix with support X, computing such an approximation can be done in time
O (r X log n + nr 2) using the randomized SVD procedure in
[45]. Each step of gradient descent requires computing the gradient and the projection onto L and R . Both of them only involve
operations on sparse matrices supported on X and thin matrices, and can be done in time O ^r X + nr 2h. Therefore, projected gradient descent achieves f-accuracy with running time
O ^r X log n log (1/f)h.

Remark 2
In the noisy setting, the algorithms can be applied without
change, and the same error bounds hold with an additional term
that depends on the noise. For matrix completion [49], this term
is r PX (W ) /p, where PX (W ) is the noise matrix supported
on the observed indices. This term can be bounded under various noise models. For example, when W has i.i.d. Gaussian or
! v entries with zero mean and variance v 2, then PX (W ) K
v p (n 1 + n 2) with high probability. The resulting error bound
is optimal in an information-theoretic sense [9]. See also [67] for
the near-optimal error control in the spectral norm and the
entry-wise infinity norm.

Global geometry and saddle-point escaping algorithms
A very recent line of work studies the global geometry of the
Burer-Monteiro formulation (18), as well as its computational
implications for algorithms starting at an arbitrary initial solution [54], [55], [57], [69]. These results are based on a geometric
notion called the strict saddle property [54], [70].

Definition 3 (strict saddle)

A function g (x) is said to be (e, c, g)-strict saddle, if for each x
at least one of the following holds:
dg (x) 2 $ e 2 0
■
2
■ m min ^ d g (x) h # - c 1 0
*
*
■ there exists a local minimum x such that x - x 2 # g.
In Figures 2 and 3, we provide examples of a one-dimensional function and a two-dimensional function, respectively,
that satisfy the strict saddle property in Definition 3. Intuitively,
the strict saddle property of g (x) ensures that whenever one
is not already close to a local minimum, the current solution
will have either a large gradient or a descent direction due to
the Hessian having a negative eigenvalue. Therefore, any local
search algorithms that are capable of finding such a descent

g (x ) = (x 2-1)2

Remark 1
Via a refined analysis of gradient descent, it is in fact possible to
drop the projection step onto L and R in matrix completion
without performance loss; cf. [67]. In particular, as long as
3
n r 3 log 3 (n 1 + n 2)
p $ C 0 (n 1 + n 2) , for some constant C, gradient descent converges geometrically and needs T = O (log (1/f)) iterations to
reach e-accuracy for the reconstruction error measured not only
in the Frobenius norm Lt R tT - X F , but also in the spectral
norm Lt R tT - X and the entry-wise infinity norm
Lt R tT - X 3 . For the SVP algorithm (21), geometric convergence in entry-wise infinity norm is also established in the work
[97] without the need of additional regularization or separate
initialization procedure.

-1

0

1

R3

R1

R2

x

Figure 2. An example of a one-dimensional strict saddle function:

g (x) = (x 2 - 1) 2 . This function has two local minima x * = 1 and x * = - 1
that are also global minima, as well as a local maximum xr = 0. In the
region R 1, the function satisfies m min ^d 2 g (x) h # - c 1 0. In the regions
R 2 and R 3, the function satisfies x - x * 2 # g for one of the local minima x *. On the rest of the real line, the function satisfies dg (x) $ e 2 0.

IEEE Signal Processing Magazine

|

July 2018

|

23



Table of Contents for the Digital Edition of IEEE Signal Processing - July 2018

Contents
IEEE Signal Processing - July 2018 - Cover1
IEEE Signal Processing - July 2018 - Cover2
IEEE Signal Processing - July 2018 - Contents
IEEE Signal Processing - July 2018 - 2
IEEE Signal Processing - July 2018 - 3
IEEE Signal Processing - July 2018 - 4
IEEE Signal Processing - July 2018 - 5
IEEE Signal Processing - July 2018 - 6
IEEE Signal Processing - July 2018 - 7
IEEE Signal Processing - July 2018 - 8
IEEE Signal Processing - July 2018 - 9
IEEE Signal Processing - July 2018 - 10
IEEE Signal Processing - July 2018 - 11
IEEE Signal Processing - July 2018 - 12
IEEE Signal Processing - July 2018 - 13
IEEE Signal Processing - July 2018 - 14
IEEE Signal Processing - July 2018 - 15
IEEE Signal Processing - July 2018 - 16
IEEE Signal Processing - July 2018 - 17
IEEE Signal Processing - July 2018 - 18
IEEE Signal Processing - July 2018 - 19
IEEE Signal Processing - July 2018 - 20
IEEE Signal Processing - July 2018 - 21
IEEE Signal Processing - July 2018 - 22
IEEE Signal Processing - July 2018 - 23
IEEE Signal Processing - July 2018 - 24
IEEE Signal Processing - July 2018 - 25
IEEE Signal Processing - July 2018 - 26
IEEE Signal Processing - July 2018 - 27
IEEE Signal Processing - July 2018 - 28
IEEE Signal Processing - July 2018 - 29
IEEE Signal Processing - July 2018 - 30
IEEE Signal Processing - July 2018 - 31
IEEE Signal Processing - July 2018 - 32
IEEE Signal Processing - July 2018 - 33
IEEE Signal Processing - July 2018 - 34
IEEE Signal Processing - July 2018 - 35
IEEE Signal Processing - July 2018 - 36
IEEE Signal Processing - July 2018 - 37
IEEE Signal Processing - July 2018 - 38
IEEE Signal Processing - July 2018 - 39
IEEE Signal Processing - July 2018 - 40
IEEE Signal Processing - July 2018 - 41
IEEE Signal Processing - July 2018 - 42
IEEE Signal Processing - July 2018 - 43
IEEE Signal Processing - July 2018 - 44
IEEE Signal Processing - July 2018 - 45
IEEE Signal Processing - July 2018 - 46
IEEE Signal Processing - July 2018 - 47
IEEE Signal Processing - July 2018 - 48
IEEE Signal Processing - July 2018 - 49
IEEE Signal Processing - July 2018 - 50
IEEE Signal Processing - July 2018 - 51
IEEE Signal Processing - July 2018 - 52
IEEE Signal Processing - July 2018 - 53
IEEE Signal Processing - July 2018 - 54
IEEE Signal Processing - July 2018 - 55
IEEE Signal Processing - July 2018 - 56
IEEE Signal Processing - July 2018 - 57
IEEE Signal Processing - July 2018 - 58
IEEE Signal Processing - July 2018 - 59
IEEE Signal Processing - July 2018 - 60
IEEE Signal Processing - July 2018 - 61
IEEE Signal Processing - July 2018 - 62
IEEE Signal Processing - July 2018 - 63
IEEE Signal Processing - July 2018 - 64
IEEE Signal Processing - July 2018 - 65
IEEE Signal Processing - July 2018 - 66
IEEE Signal Processing - July 2018 - 67
IEEE Signal Processing - July 2018 - 68
IEEE Signal Processing - July 2018 - 69
IEEE Signal Processing - July 2018 - 70
IEEE Signal Processing - July 2018 - 71
IEEE Signal Processing - July 2018 - 72
IEEE Signal Processing - July 2018 - 73
IEEE Signal Processing - July 2018 - 74
IEEE Signal Processing - July 2018 - 75
IEEE Signal Processing - July 2018 - 76
IEEE Signal Processing - July 2018 - 77
IEEE Signal Processing - July 2018 - 78
IEEE Signal Processing - July 2018 - 79
IEEE Signal Processing - July 2018 - 80
IEEE Signal Processing - July 2018 - 81
IEEE Signal Processing - July 2018 - 82
IEEE Signal Processing - July 2018 - 83
IEEE Signal Processing - July 2018 - 84
IEEE Signal Processing - July 2018 - 85
IEEE Signal Processing - July 2018 - 86
IEEE Signal Processing - July 2018 - 87
IEEE Signal Processing - July 2018 - 88
IEEE Signal Processing - July 2018 - 89
IEEE Signal Processing - July 2018 - 90
IEEE Signal Processing - July 2018 - 91
IEEE Signal Processing - July 2018 - 92
IEEE Signal Processing - July 2018 - 93
IEEE Signal Processing - July 2018 - 94
IEEE Signal Processing - July 2018 - 95
IEEE Signal Processing - July 2018 - 96
IEEE Signal Processing - July 2018 - 97
IEEE Signal Processing - July 2018 - 98
IEEE Signal Processing - July 2018 - 99
IEEE Signal Processing - July 2018 - 100
IEEE Signal Processing - July 2018 - 101
IEEE Signal Processing - July 2018 - 102
IEEE Signal Processing - July 2018 - 103
IEEE Signal Processing - July 2018 - 104
IEEE Signal Processing - July 2018 - 105
IEEE Signal Processing - July 2018 - 106
IEEE Signal Processing - July 2018 - 107
IEEE Signal Processing - July 2018 - 108
IEEE Signal Processing - July 2018 - 109
IEEE Signal Processing - July 2018 - 110
IEEE Signal Processing - July 2018 - 111
IEEE Signal Processing - July 2018 - 112
IEEE Signal Processing - July 2018 - 113
IEEE Signal Processing - July 2018 - 114
IEEE Signal Processing - July 2018 - 115
IEEE Signal Processing - July 2018 - 116
IEEE Signal Processing - July 2018 - 117
IEEE Signal Processing - July 2018 - 118
IEEE Signal Processing - July 2018 - 119
IEEE Signal Processing - July 2018 - 120
IEEE Signal Processing - July 2018 - 121
IEEE Signal Processing - July 2018 - 122
IEEE Signal Processing - July 2018 - 123
IEEE Signal Processing - July 2018 - 124
IEEE Signal Processing - July 2018 - 125
IEEE Signal Processing - July 2018 - 126
IEEE Signal Processing - July 2018 - 127
IEEE Signal Processing - July 2018 - 128
IEEE Signal Processing - July 2018 - 129
IEEE Signal Processing - July 2018 - 130
IEEE Signal Processing - July 2018 - 131
IEEE Signal Processing - July 2018 - 132
IEEE Signal Processing - July 2018 - 133
IEEE Signal Processing - July 2018 - 134
IEEE Signal Processing - July 2018 - 135
IEEE Signal Processing - July 2018 - 136
IEEE Signal Processing - July 2018 - 137
IEEE Signal Processing - July 2018 - 138
IEEE Signal Processing - July 2018 - 139
IEEE Signal Processing - July 2018 - 140
IEEE Signal Processing - July 2018 - Cover3
IEEE Signal Processing - July 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com