Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion

ABSTRACT

We consider the problem of performing matrix completion with side information on row-by-row and column-by-column similarities. We build upon recent proposals for matrix estimation with smoothness constraints with respect to row and column graphs. We present a novel iterative procedure for directly minimizing an information criterion to select an appropriate amount of row and column smoothing, namely, to perform model selection. We also discuss how to exploit the special structure of the problem to scale up the estimation and model selection procedure via the Hutchinson estimator, combined with a stochastic Quasi-Newton approach. Supplementary material for this article is available online.

KEYWORDS:

• Convex optimization
• Degrees of freedom
• Hutchinson estimator
• Information criterion
• Penalization
• Sparse linear systems

Supplementary Materials

• Algorithm derivations, additional examples, and proofs: The supplemental materials includes additional details on derivations needed to implement the Quasi-Newton method, additional simulation, and real data experiments, as well as all proofs of results in Section 3 and Section 5.

• Code: Matlab code implementing IMS and scripts for regenerating the numerical results are available at https://github.com/echi/IMS.

Acknowledgments

The authors thank Salman Asif and Chris Harshaw for their help on a prior project from which this current work arose. All plots were made using R (R Core Team 2013) and the R package ggplot2 (Wickham 2009).

Additional information

Funding

EC was supported by the NCSU Faculty Research and Professional Development (FRPD) program. AR was supported by a gift from Agilent technologies, NIH R01 CA214955, CPRIT grants RP150578, RP170719 and a Research Scholar Grant from the American Cancer Society (RSG-16-005-01).