Low-Rank Matrix Approximation Using Point-Wise Operators

The problem of extracting low-dimensional structure from high-dimensional data arises in many applications such as machine learning, statistical pattern recognition, wireless sensor networks, and data compression. If the data is restricted to a lower dimensional subspace, then simple algorithms using linear projections can find the subspace and consequently estimate its dimensionality. However, if the data lies on a low-dimensional but nonlinear space (e.g., manifolds), then its structure may be highly nonlinear and, hence, linear methods are doomed to fail. In this paper, we introduce a new technique for dimensionality reduction based on point-wise operators. More precisely, let be a matrix of rank and assume that the matrix is generated by taking the elements of to some real power . In this paper, we show that based on the values of the data matrix , one can estimate the value and, therefore, the underlying low-rank matrix ; i.e., we are reducing the dimensionality of by using point-wise operators. Moreover, the estimation algorithm does not need to know the rank of . We also provide bounds on the quality of the approximation and validate the stability of the proposed algorithm with simulations in noisy environments.