## Rank Determination for Low-Rank Data Completion

*Morteza Ashraphijuo, Xiaodong Wang, Vaneet Aggarwal*; 18(98):1−29, 2017.

### Abstract

Recently, fundamental conditions on the sampling patterns have
been obtained for finite completability of low-rank matrices or
tensors given the corresponding ranks. In this paper, we
consider the scenario where the rank is not given and we aim to
approximate the unknown rank based on the location of sampled
entries and some given completion. We consider a number of data
models, including single-view matrix, multi-view matrix, CP
tensor, tensor-train tensor and Tucker tensor. For each of these
data models, we provide an upper bound on the rank when an
arbitrary low-rank completion is given. We characterize these
bounds both deterministically, i.e., with probability one given
that the sampling pattern satisfies certain combinatorial
properties, and probabilistically, i.e., with high probability
given that the sampling probability is above some threshold.
Moreover, for both single-view matrix and CP tensor, we are able
to show that the obtained upper bound is exactly equal to the
unknown rank if the lowest-rank completion is given.
Furthermore, we provide numerical experiments for the case of
single-view matrix, where we use nuclear norm minimization to
find a low-rank completion of the sampled data and we observe
that in most of the cases the proposed upper bound on the rank
is equal to the true rank.

[abs][pdf][bib]