Deterministic and Probabilistic Conditions for Finite Completability of Low-rank Multi-View Data

We consider the multi-view data completion problem, i.e., to complete a matrix $\mathbf{U}=[\mathbf{U}_1|\mathbf{U}_2]$ where the ranks of $\mathbf{U},\mathbf{U}_1$, and $\mathbf{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. In contrast with the existing analysis on Grassmannian manifold for a single-view matrix, i.e., conventional matrix completion, we propose a geometric analysis on the manifold structure for multi-view data to incorporate more than one rank constraint. We provide a deterministic necessary and sufficient condition on the sampling pattern for finite completability. We also give a probabilistic condition in terms of the number of samples per column that guarantees finite completability with high probability. Finally, using the developed tools, we derive the deterministic and probabilistic guarantees for unique completability.

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-01-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1701.00737
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Characterization of Deterministic and Probabilistic Sampling Patterns for Finite Completability of Low Tensor-Train Rank Tensor

  2017cited by this paper
• Fundamental Conditions for Low-CP-Rank Tensor Completion

  2017cited by this paper
• Tensor Completion by Alternating Minimization under the Tensor Train (TT) Model

  2016cited by this paper
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor

  2016cited by this paper
• Deterministic and Probabilistic Conditions for Finite Completability of Low Rank Tensor

  2016influential reference
• Characterization of rank-constrained feasibility problems via a finite number of convex programs

  2016cited by this paper
• Tensor completion via adaptive sampling of tensor fibers: Application to efficient indoor RF fingerprinting

  2016cited by this paper
• Adaptive Sampling of RF Fingerprints for Fine-Grained Indoor Localization

  2015cited by this paper
• Low-Rank Multi-View Learning in Matrix Completion for Multi-Label Image Classification

  2015cited by this paper
• A characterization of deterministic sampling patterns for low-rank matrix completion

  2015influential reference
• A Survey on Multi-view Learning

  2013cited by this paper
• Understanding Alternating Minimization for Matrix Completion

  2013cited by this paper
• Low-rank matrix completion using alternating minimization

  2012cited by this paper
• On Combining Multiple Features for Hyperspectral Remote Sensing Image Classification

  2012cited by this paper
• The algebraic combinatorial approach for low-rank matrix completion

  2012cited by this paper
• View Generation for Multiview Maximum Disagreement Based Active Learning for Hyperspectral Image Classification

  2012cited by this paper
• Semisupervised Multiview Distance Metric Learning for Cartoon Synthesis

  2012cited by this paper
• Multi-View Learning of Word Embeddings via CCA

  2011cited by this paper
• Email classification with co-training

  2011cited by this paper
• Multiple Kernel Learning Algorithms

  2011cited by this paper
• Co-regularized Multi-view Spectral Clustering

  2011cited by this paper
• Sparse Multiple Kernel Learning for Signal Processing Applications

  2010cited by this paper
• Robust video denoising using low rank matrix completion

  2010cited by this paper
• The Power of Convex Relaxation: Near-Optimal Matrix Completion

  2009cited by this paper
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images

  2009cited by this paper
• Learning from Multiple Partially Observed Views - an Application to Multilingual Text Categorization

  2009cited by this paper
• Multi-view clustering via canonical correlation analysis

  2009cited by this paper
• An RKHS for multi-view learning and manifold co-regularization

  2008cited by this paper
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• Multi-View Learning in the Presence of View Disagreement

  2008cited by this paper
• A Singular Value Thresholding Algorithm for Matrix Completion

  2008cited by this paper
• Asymmetric bagging and random subspace for support vector machines-based relevance feedback in image retrieval

  2006cited by this paper
• Multi-view Semi-supervised Learning: An Approach to Obtain Different Views from Text Datasets

  2005cited by this paper
• Two view learning: SVM-2K, Theory and Practice

  2005cited by this paper
• Deterministic network coding by matrix completion

  2005cited by this paper
• Learning Shared Latent Structure for Image Synthesis and Robotic Imitation

  2005cited by this paper
• Multiple kernel learning, conic duality, and the SMO algorithm

  2004cited by this paper
• Multi-view clustering

  2004cited by this paper
• SOLVING SYSTEMS OF POLYNOMIAL EQUATIONS

  2002cited by this paper
• High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality

  2000cited by this paper

• A Perturbation Bound on the Subspace Estimator from Canonical Projections

  2022cites this paper
• Fundamental conditions on the sampling pattern for union of low-rank subspaces retrieval

  2019influential citation
• A Characterization of Sampling Patterns for Union of Low-Rank Subspaces Retrieval Problem

  2018influential citation
• An approximation of the CP-rank of a partially sampled tensor

  2017cites this paper
• On Deterministic Sampling Patterns for Robust Low-Rank Matrix Completion

  2017cites this paper
• Fundamental Conditions for Low-CP-Rank Tensor Completion

  2017cites this paper
• Characterization of Deterministic and Probabilistic Sampling Patterns for Finite Completability of Low Tensor-Train Rank Tensor

  2017cites this paper
• A characterization of sampling patterns for low-rank multi-view data completion problem

  2017cites this paper
• Scaled Nuclear Norm Minimization for Low-Rank Tensor Completion

  2017cites this paper
• Rank Determination for Low-Rank Data Completion

  2017influential citation
• A characterization of sampling patterns for low-tucker-rank tensor completion problem

  2017cites this paper