Fundamental sampling patterns for low-rank multi-view data completion

PATTERN RECOGNITION

卷:103

Article

Ashraphijuo, Morteza¹  Wang, Xiaodong¹  Aggarwal, Vaneet² 

[1] Columbia Univ, Dept Elect Engn, New York, NY 10027 USA

[2] Purdue Univ, Sch Ind Engn, W Lafayette, IN 47907 USA

关键词: Multi-view learning;    Low-rank matrix completion;    Sampling pattern;    Sampling rate;    Non-convex optimization;    Rank decomposition;   

DOI  :  10.1016/j.patcog.2020.107307

来源: Elsevier

【 摘 要 】

We consider the multi-view data completion problem, i.e., to complete a matrix U = [U-1 vertical bar U-2] where the ranks of U, U-1, and U-2 are given. In particular, we investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries for finite completability of such a multi-view data given the corresponding rank constraints. We provide a geometric analysis on the manifold structure for multi-view data to incorporate more than one rank constraint. We derive a probabilistic condition in terms of the number of samples per column that guarantees finite completability with high probability. Finally, we derive the guarantees for unique completability. Numerical results demonstrate reduced sampling complexity when the multi-view structure is taken into account as compared to when only low-rank structure of individual views is taken into account. Then, we propose an apporach using Newton's method to almost achieve these information-theoretic bounds for mulit-view data retrieval by taking advantage of the rank decomposition and the analysis in this work. (C) 2020 Elsevier Ltd. All rights reserved.

【 授权许可】

Free