  The problem of Knowledge Base Completion can be framed as a 3rd-order binary
tensor completion problem. In this light, the Canonical Tensor Decomposition
(CP) (Hitchcock, 1927) seems like a natural solution; however, current
implementations of CP on standard Knowledge Base Completion benchmarks are
lagging behind their competitors. In this work, we attempt to understand the
limits of CP for knowledge base completion. First, we motivate and test a novel
regularizer, based on tensor nuclear $p$-norms. Then, we present a
reformulation of the problem that makes it invariant to arbitrary choices in
the inclusion of predicates or their reciprocals in the dataset. These two
methods combined allow us to beat the current state of the art on several
datasets with a CP decomposition, and obtain even better results using the more
advanced ComplEx model.
