Robust low-rank tensor factorization by cyclic weighted median

Low-rank tensor factorization (LRTF) provides a useful mathematical tool to reveal and analyze multi-factor structures underlying data in a wide range of practical applications. One challenging issue in LRTF is how to recover a low-rank higher-order representation of the given high dimensional data in the presence of outliers and missing entries, i.e., the so-called robust LRTF problem. The L1-norm LRTF is a popular strategy for robust LRTF due to its intrinsic robustness to heavy-tailed noises and outliers. However, few L1-norm LRTF algorithms have been developed due to its non-convexity and non-smoothness, as well as the high order structure of data. In this paper we propose a novel cyclic weighted median (CWM) method to solve the L1-norm LRTF problem. The main idea is to recursively optimize each coordinate involved in the L1-norm LRTF problem with all the others fixed. Each of these single-scalar-parameter sub-problems is convex and can be easily solved by weighted median filter, and thus an effective algorithm can be readily constructed to tackle the original complex problem. Our extensive experiments on synthetic data and real face data demonstrate that the proposed method performs more robust than previous methods in the presence of outliers and/or missing entries.