IEEE Signal Processing - July 2018 - 19
possess certain desirable properties so that it can distinguish
different low-rank matrices. One such property is called the
restricted isometry property (RIP). RIP stipulates that A,
viewed as a mapping to a lower-dimensional space, preserves
the Euclidean distances between low-rank matrices. Next, we
give a general notion of RIP, where the distances after mapping may be measured in different norms.
Definition 1: RIP
The operator A is said to satisfy the RIP- , 2 /, p property
of rank r, if for all matrices U of rank at most r, it satisfies
the inequality
(1 - d r) U
F
# A ^Uh
p
# (1 + dr r) U F,
Guarantees for matrix completion via incoherence
In the case of matrix completion, an additional complication
arises: it is impossible to recover a low-rank matrix that is
also sparse. In particular, when one only samples a small subset of the entries of X, it is very likely that most, if not all, of
the nonzero entries of X are missed. This means that the
sensing operator A = PX used for matrix completion cannot
satisfy the RIP. Therefore, for the problem to be well posed,
we need to restrict attention to low-rank matrices whose mass
does not concentrate on a few entries. This property can be
formalized by the notion of incoherence, which measures the
alignment between the column/row spaces of the low-rank
matrix with the standard basis vectors.
Definition 2: Incoherence
For a matrix U ! R n # r with orthonormal columns, let PU be
the orthogonal projection onto the column space of U. The
incoherence parameter of U is defined as
where d r and dr r are some universal constants satisfying
0 1 1 - dr 1 1 1 1 + dr .
This definition is reminiscent of a similar notion with the
same name used in the sparse signal recovery literature that is
imposed on sparse vectors [1]. Certifying whether RIP holds
for a given operator is known to be NP-hard [26]. Nevertheless,
it turns out that a "generic" sensing operator, drawn from certain random distributions, satisfies RIP with high probability.
For example:
■ If the measurement matrix A l has independent and identically distributed (i.i.d.) Gaussian entries N (0, 1/m), then
A satisfies RIP- , 2 /, 2 with high probability as long as
m $ c (n 1 + n 2) r for some large enough constant c 2 0
[25], [27].
T
■ If the measurement matrix A l = a l b l is rank-1 with a l, b l
composed with i.i.d. Gaussian entries N (0, 1/m), then
A satisfies RIP- , 2 /, 1 with high probability as long as
m $ c (n 1 + n 2) r for some large enough constant c 2 0
[28], [29].
When RIP- , 2 /, p holds, the nuclear norm minimization approach guarantees exact and stable recovery of the low-rank
matrix in both noise-free and noisy cases, as shown in the following theorem adapted from [27]-[29].
It is easy to see that the incoherence parameter satisfies the bound 1 # n (U ) # n/r. With a smaller n (U ), the column space of U is more spread out over its coordinates. For
a matrix X, its incoherence parameters n 0 are determined
by the singular vectors and are independent of its singular
values. In the noiseless setting, nuclear norm minimization
can perfectly recover an incoherent low-rank matrix as soon
as the number of measurements is slightly larger than the
degrees of freedom of the matrix. Such recovery guarantees
were proved and refined in a series of work in [8], [10], [11],
and [31]-[33]. Theorem 2 is adapted from [31], which is state
of the art.
Theorem 1 (Recovery guarantee via RIP)
Theorem 2 (Recovery guarantee via incoherence)
Suppose that the noise satisfies w p # e. If A satisfies RIP, 2 /, p , then the solution to the nuclear norm minimization
algorithms (9)-(11) (with appropriate values for the tuning
parameters) satisfies the error bound
Suppose that each entry of X is observed independently with
probability p ! (0, 1). If p satisfies
Xt - X
F
# C1
X - Xr
r
*
+ C2 e
n (U ) =
n max P e 2 .
r 1#i#n U i 2
(14)
For a matrix with the SVD X = URV T , the incoherence
parameter of X is defined as
n 0 = max {n (U ), n (V )}.
p $ Cn 0
r log 2 (n 1 + n 2)
,
(n 1 + n 2)
(13)
simultaneously for all X ! R n 1 # n 2, where C 1 and C 2 are positive numerical constants. When p = 2 we require dr 4r 1
0.1892, d 4r 1 0.2346 [27]; when p = 1, we require that there
exists a universal constant k $ 2 such that (1 + dr kr) /
(1 - d kr) 1 k [28], [29]. Both requirements can be met
with a sample complexity of O ((n 1 + n 2) r) .
For studying the performance of nuclear norm minimization via other notions such as the null space property,
see [30].
for some constant C, then, with high probability, the nuclear
norm minimization algorithm (9) exactly recovers X as the
unique optimal solution.
By a coupon-collecting argument [8], one can, in fact,
show that it is impossible to recover the matrix with fewer than
(n 1 + n 2) r log (n 1 + n 2) measurements using any algorithm.
Therefore, Theorem 2 shows that nuclear norm minimization
is near optimal in terms of sample complexity-off by only a
logarithmic factor-a remarkable fact considering that we are
using a convex relaxation of the rank.
IEEE Signal Processing Magazine
|
July 2018
|
19
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