Database Reference
In-Depth Information
us from computing an SVD of
X
in order to solve (
8.40
): we may simply take
B
T
to
be composed of the first
k
rows of
X
and
C
to be composed of the first
k
column unit
vectors. In other words, the desired initial guess is available right away through
“rounding”
X
itself to a feasible solution.
For more details about the connection of k-means and SVD and nonnegative
matrix factorization, we refer to the work of Chris Ding [DHS05, DLJ10].
But how exactly may clustering figure in estimating the largest entries of a
low-rank matrix? The procedure we would like to propose here is as follows: the
column set of
X
is to be divided into
k
clusters, and each of the clusters is to be
k
-clustered itself, and so on in a recursive fashion until we arrive at a partitioning
each set of which contains fewer than
k
elements. For simplicity's sake, let us take
k
:
¼
2. Imagine the recursive cluster centers to be arranged in a tree to which an
auxiliary root node connected to the two top-level cluster centers has been added.
Starting at the root, we proceed by computing the inner product of
y
and the cluster
centers corresponding to the children of the current node and move on to the child
node where the inner product is largest. Applying this criterion recursively, we
arrive at a leaf node that corresponds to a specific column
x
of
X
. Arguably,
x
T
y
should be fairly close to the greatest
x
i
y
,
i
,
m
}. Having deleted the node
pertaining to
x
from our tree, we apply the same procedure to obtain an estimate of
the second largest entry of
a
and repeat this procedure until we have gathered a
sufficient amount of large elements.
Please note that, apart from the computational cost of clustering, which needs to
be carried out only once, though, estimating the largest entry of
a
in the above-
described fashion would require only
O
(log
k
m
) rather than
O
(
m
) operations, which
makes it an appealing candidate.
By means of linear algebra, it is even possible to assess the quality of our
estimates by providing error bounds and provide a rigorous framework for the
above procedure.
Lemma 8.1
Let
(
V
,
h
,
i
)
be an inner product space. Then, for all c
,
v
,
w
{1,
...
∈
V
,
∈
h
c
;
w
i kkc v
k
k v
h
;
w
i c
h
;
w
i þ kkc v
k
k
,
; h
p
,
i.e.
, the norm induced by the inner product.
where
kk:¼
Proof
The statement
is an immediate consequence of the Cauchy-Schwarz
inequality: it holds that
j
h
v
;
w
i c
h
;
w
i
j ¼
j
h
v c
,
w
i
j
k
v c
k kk
,
which, together with the simple fact that
v
j
h
;
w
i c
h
;
w
i
j v
h
;
w
i c
h
;
w
i
j
h
v
;
w
i c
h
;
w
i
j
,
yields the desired result.
□
