Robust Rank Estimation for Noisy Matrices

Subhrajyoty Roy, Abhik Ghosh, Ayanendranath Basu · 2025

Read Robust Rank Estimation for Noisy Matrices by Subhrajyoty Roy, Abhik Ghosh, Ayanendranath Basu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19583.txt.

Introduction

Subhrajyoty Roy, Abhik Ghosh, and Ayanendranath Basu propose a new way to estimate the rank of a data matrix corrupted by noise and outliers. Rank estimation underlies tools like principal component analysis and matrix completion. Older criteria are either thrown off by outliers or become expensive when paired with robust estimators.

Their criterion, DICMR, grows out of the density power divergence framework, which is known for resisting outliers, yet stays computationally simple. The authors bound its chances of over- or under-estimating the rank and confirm its robustness formally. Simulations matched the accuracy of robust cross-validation at far lower cost, and a microarray imputation task showed the method beating several leading algorithms in practice.

Catalog record

CREATORSubhrajyoty Roy, Abhik Ghosh, Ayanendranath Basu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19583

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Robust Rank Estimation for Noisy Matrices Subhrajyoty Roy, Abhik Ghosh, Ayanendranath Basu Abstract Estimating the true rank of a noisy data matrix is a fundamental problem underlying techniques such as principal component analysis, matrix completion, etc. Existing rank estimation criteria, including information-based and cross-validation methods, are either highly sensitive to outliers or computationally demanding when combined with robust estimators. This paper proposes a new criterion, the Divergence Information Criterion for Matrix Rank (DICMR), that achieves both robustness and computational simplicity. Derived from the density power divergence framework, DICMR inherits the robustness properties while being computationally very simple. We provide asymptotic bounds on its overestimation and underestimation probabilities, and demonstrate first-order B-robustness of the criteria. Extensive simulations show that DICMR delivers accuracy comparable to the robustified cross-validation methods, but with far lower computational cost. We also showcase a real-data application to microarray imputation to further demonstrate its practical utility, outperforming several state-of-the-art algorithms. Keywords: Robust Principal Component Analysis, Model Selection, Minimum Divergence Estimation. 1 Introduction Numerous statistical tools have been developed to analyze the structure of a dataset represented in a matrix form. A common challenge in applying some of these tools, such as the Singular Value Decomposition (SVD), Principal Component Analysis (PCA), Non-negative Matrix Factorization (NMF), Matrix Completion (MC), etc. is the determination of the true rank of the data matrix. In some applications, this true rank can be guessed based on the domain knowledge or external data (e.g. rank is usually taken as 1 or 2 in the problem of video background modelling [ Roy et al. 2024b ] ), while some studies completely avoid them [ Choi et al. 2025 ] . However, in most applications, this rank is not known and must be estimated in a data-dependent fashion [ Greenacre et al. 2022 ] . For example, in various genome-wide studies, one often works with a microarray data which is partially observed [ Moorthy et al. 2019 ] . To impute these missing values, a standard technique is to assume a low-rank structure of the entire data matrix, estimate this low-rank component based on observed entries and use that to derive the imputed values. In this case, the quality of imputation is greatly affected by the choice of the rank of this low-rank component. Although the number of patients or clusters of cells may be known from exogeneous datasets, the relationships between various genes are not known during collection of the microarray data (e.g., RNA sequencing), which limits the ability to guess the true rank beforehand. Later in Section 6 , we demonstrate one such example of how the method proposed in this paper can be used to obtain a robust estimate of the rank of the low-rank component to solve the microarray data imputation problem. There are primarily three branches of methods for the determination of the rank: subjective and ad hoc methods (e.g. scree plot), distribution based methods (e.g. information criterion, and thresholding) and computational methods (e.g. cross-validation); see Jolliffe 2002 for a summary. Unfortunately, none of these existing methods are resistant to outliers. As will be shown later in Section 5 , a naive approach of replacing the classical SVD or PCA procedures with robust SVD or PCA procedures either does not provide a reliable estimate of the rank, or significantly increases the computational cost. In this paper, we aim to address this gap by proposing a novel rank estimation method which is both robust and computationally simple. 1.1 Mathematical Description of the Problem Before we present the existing methods for determination of the matrix rank, let us first present the mathematical formulation of the problem. We are provided with an n\times p data matrix \boldsymbol{X} that decomposes into a low-rank component \boldsymbol{L} , a sparse component \boldsymbol{S} and a dense perturbation component \boldsymbol{N} as \boldsymbol{X}=\boldsymbol{L}+\boldsymbol{S}+\dfrac{\sigma}{\sqrt{\max\{n,p\}}}\boldsymbol{N}. (1) Here, the noise matrix \boldsymbol{N} is composed of i.i.d. entries with some unknown density function g such that \mathbb{E}(n_{ij})=0 and \mathrm{Var}(n_{ij})=1 for all i=1,2,\dots,n and j=1,2,\dots,p and \sigma is the common noise variance. Given the data matrix \boldsymbol{X} , the objective is then to robustly estimate r=\text{Rank}\left(\boldsymbol{L}\right) . The decomposition given in ( 1 ) arises in many applications, such as robust PCA [ Roy et al. 2024a ] , robust SVD [ Roy et al. 2024b ] , NMF [ Cichocki et al. 2011 ] , clustering analysis [ Du et al. 2017 ] , image processing [ Sadek 2012 ] , etc. It is worthwhile to note that the scaling factor of 1/\sqrt{\max\{n,p\}} in the noise component is necessary to ensure identifiability of this rank estimation problem. As shown in Candès et al. 2011 , if the noise variance does not asymptotically go to 0 as either n or p increases to infinity, the largest singular value of the noise matrix \boldsymbol{N} and its corresponding singular vectors can be added to \boldsymbol{L} to constitute a new low-rank component with a different rank than that of \boldsymbol{L} . Additionally, Shabalin and Nobel 2013 proved that any reasonable matrix decomposition technique cannot consistently estimate the singular values of \boldsymbol{L} (or its functions like the rank, i.e., the number of nonzero singular values) from the data matrix \boldsymbol{X} if the noise variance is larger than the order of 1/\sqrt{np} . The same scaling factor also appears in Assumption (B6) employed in the proof of the consistency of the rSVDdpd estimator [ Roy et al. 2024b ] , which we shall make use of later. 1.2 Organization of the paper In this paper, we propose a novel matrix rank estimation criterion called divergence information criterion for matrix rank (DICMR) based on the divergence information criterion (DIC) by Karagrigoriou and Papaioannou 2008 . The criterion is derived in Section 3 . Prior to that, we briefly review various existing rank estimation techniques in Section 2 . Section 4 deals with establishing theoretical properties of the proposed criterion, including selection consistency and influence function analysis. The proposed method is resistant to outlying observations, achieves a performance similar to (if not better than) various cross-validation methods, while remaining computationally simple and efficient. This has been demonstrated through extensive simulation studies in Section 5 . Finally, in Section 6 , we showcase a real use-case of the proposed method for the microarray data imputation problem and also compare it against several existing imputation algorithms. The proposed method is found to be superior in accuracy than these other existing methods. Due to the space constraints, all proofs of the theoretical results are provided in Section A of the Appendix. 2 Existing Literature 2.1 Penalization Methods As discussed in Section 1 , one of the major classes of techniques used to determine the rank of a matrix is distribution-based methods such as information criteria, thresholding, etc. These methods are usually built by combining a statistical discrepancy measure of fit from a partial SVD estimate to the data matrix \boldsymbol{X} and a penalty function of the rank used in the partial SVD estimate. Hence, we refer to such methods as penalization methods. As one includes higher rank components in the estimate, the error in estimation reduces by yielding a small discrepancy measure, but the penalty function compensates by being an increasing function of the rank. Mathematically,

Read the complete text