We propose a novel technique for finding representatives from a large, unsupervised dataset. The approach is based on the concept of self-rank, defined as the minimum number of samples needed to reconstruct all samples with an accuracy proportional to the rank-$K$ approximation. Our proposed algorithm enjoys linear complexity w.r.t. the size of original dataset and simultaneously it provides an adaptive upper bound for approximation ratio. These favorable characteristics result in filling a historical gap between practical and theoretical methods in finding representatives.

The linear system with missing information is investigated in this paper. New methods are introduced to improve the Mean Squared Error (MSE) on the test set in comparison to state-of-the-art method s, through appropriate tuning of Bias-Variance trade-off. The concept is to cluster the data and adapt the learning model to each cluster. Hence, we set forth a controlled bias into the problem and positively utilize it to enhance learning capability on the instances considered in some specific neighborhood. To deal with missing infrormation, we propose a novel algorithm “Missing-SCOP” based on SCOP-KMEANS algorithm introduced by Wagstaff, et al., utilizing the missing pattern of the dataset for construction of a soft-constraint matrix and clustering in missing scenario. It is shown that controlled over-fitting suggested by our algorithm improves prediction accuracy in various cases. Numerical experiments approve the efficacy of our proposed algorithm in enhancing the prediction accuracy.