fLRR: fast low‐rank representation using Frobenius‐norm

Abstract

Low‐rank representation (LRR) intends to find the representation with lowest rank of a given data set, which can be formulated as a rank‐minimisation problem. Since the rank operator is non‐convex and discontinuous, most of the recent works use the nuclear norm as a convex relaxation. It is theoretically shown that, under some conditions, the Frobenius‐norm‐based optimisation problem has a unique solution that is also a solution of the original LRR optimisation problem. In other words, it is feasible to apply the Frobenius norm as a surrogate of the non‐convex matrix rank function. This replacement will largely reduce the time costs for obtaining the lowest‐rank solution. Experimental results show that the method (i.e. fast LRR (fLRR)) performs well in terms of accuracy and computation speed in image clustering and motion segmentation compared with nuclear‐norm‐based LRR algorithm.