Authors: X. Shu (University of Illinois, Urbana-Champaign, USA), F. Porikli (Australian National University/NICTA, Australia), Narendra Ahuja (University of Illinois, Urbana-Champaign, USA)
Chapter Description
Learning and exploiting a low-rank structure from the corrupted observation is widely used in machine learning, data mining, and computer vision. This chapter gives a brief overview of two kinds of low-rank recovery methods—convex nuclear-norm based methods and non-convex matrix factorization methods. In general, convex nuclear-norm based methods are guaranteed to be reach the global minima with cubic computational complexity, while non-convex matrix factorization methods are more computationally efficient (quadratic complexity) but suffers from poor convergence. Motivated by these two kinds of low-rank recovery methods, this chapter introduces a computationally efficient low-rank recovery method, called Robust Orthonormal Subspace Learning (ROSL). Different from convex methods using nuclear norm, ROSL utilizes a novel rank measure on the low-rank matrix that imposes the group sparsity of its coefficients under orthonormal subspace. This new rank measure is proven to be lower bounded by (i.e., has the same global minimum as) nuclear norm and is experimentally shown to converge to its global minimum with high probability. In addition, this chapter also describes a faster version (ROSL+) empowered by random sampling, which further speeds up ROSL from quadratic complexity to linear complexity.