let us define the following measure.

\[def:rom\] Rank-oneness measure (ROM) of a rank $R$ matrix $\boldsymbol{A}$ with singular values $\sigma_1, \sigma_2, \ldots, \sigma_R$ is defined as

$$\small
ROM(\boldsymbol{A})=\sqrt{\frac{\sigma_1^2}{\sum_{r=1}^R \sigma_r^2 }}=\frac{\sigma_1}{\|\boldsymbol{A}\|_F}.$$

\[pr:rom\] Assume the rows of $\boldsymbol{A}$ are normalized to lie on the unit sphere. There exists at least one data point, $i$, such that the correlation coefficient between $\boldsymbol{a_i}$ and the first right singular vector of $\boldsymbol{A}$ is greater than or equal to $\it{ROM}(\boldsymbol{A})$.

Robustness to Perturbation
--------------------------

Data selection algorithms are vulnerable to outlier samples. Since outlier samples are more spread in the space of data, their span covers a wider subspace. However, the spanned subspace by outliers may not be a proper representative subspace. DS3 adds a penalty to the cost function in order to reject outliers [@Elhamifar2016DissimilaritySelection]. Our proposed algorithm computes the first singular vector as the leading direction in each iteration. We show here that this direction is the most robust spectral component against changes in the data. First consider the autocorrelation matrix of data defined as,

\[lem:sens\] Assume square matrix $\boldsymbol{C}$ and its spectrum $[\lambda_i, v_i]$. Then, the following inequality holds,

\[pr:sens2\] Assume square matrix $\boldsymbol{C}$ and its spectrum $[\lambda_i, v_i]$, where the gap between 