Hadamard Extensions and the Identification of Mixtures of Product Distributions

The Hadamard Extension <inline-formula> <tex-math notation="LaTeX">$\mathbb H({\mathrm {m}})$ </tex-math></inline-formula> of an <inline-formula> <tex-math notation="LaTeX">$n \times k$ </tex-math></inline-formula> matrix m is the collection of all Hadamard products of subsets of its rows. This construction is essential for source identification (parameter estimation) of a mixture of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> product distributions over <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> binary random variables. A necessary requirement for such identification is that <inline-formula> <tex-math notation="LaTeX">$\mathbb H({\mathrm {m}})$ </tex-math></inline-formula> have full column rank; conversely, identification is possible if apart from each row there exist two disjoint sets of rows of m, each of whose extension has full column rank. It is necessary therefore to understand when <inline-formula> <tex-math notation="LaTeX">$\mathbb H({\mathrm {m}})$ </tex-math></inline-formula> has full column rank; we provide two results in this direction. The first is that if <inline-formula> <tex-math notation="LaTeX">$\mathbb H({\mathrm {m}})$ </tex-math></inline-formula> has full column rank then there exists a set of at most <inline-formula> <tex-math notation="LaTeX">$k-1$ </tex-math></inline-formula> rows of m, whose extension already has full column rank. The second is a Hall-type condition on the values in the rows of m, that suffices to ensure full column rank of <inline-formula> <tex-math notation="LaTeX">$\mathbb H({\mathrm {m}})$ </tex-math></inline-formula>.

• Publication year

  2021

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2021-01-27

• Fields of study

  Mathematics, Physics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/tit.2022.3146630arXiv 2101.11688
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Source Identification for Mixtures of Product Distributions

  2020cited by this paper
• Beyond the low-degree algorithm: mixtures of subcubes and their applications

  2018influential reference
• On the Identifiability of Parameters in the Population Stratification Problem: A Worst-Case Analysis

  2018cited by this paper
• On the Identifiability of Finite Mixtures of Finite Product Measures

  2018cited by this paper
• Learning Arbitrary Statistical Mixtures of Discrete Distributions

  2015cited by this paper
• Learning mixtures of arbitrary distributions over large discrete domains

  2012cited by this paper
• A Method of Moments for Mixture Models and Hidden Markov Models

  2012cited by this paper
• Learning Mixtures of Product Distributions Using Correlations and Independence

  2008cited by this paper
• Finite Mixture Models

  2008cited by this paper
• Learning mixtures of product distributions over discrete domains

  2005cited by this paper
• Estimating a mixture of two product distributions

  1999cited by this paper
• Evolutionary trees can be learned in polynomial time in the two-state general Markov model

  1998cited by this paper
• Mixture models : theory, geometry, and applications

  1995cited by this paper
• On the learnability of discrete distributions

  1994cited by this paper
• Statistical analysis of finite mixture distributions

  1986cited by this paper
• Mixtures of discrete distributions

  1981cited by this paper
• A Generalized Theory of the Combination of Observations so as to Obtain the Best Result

  1886cited by this paper
• III. Contributions to the mathematical theory of evolution

  year unknowncited by this paper

• Identifiability and Estimation in High-Dimensional Nonparametric Latent Structure Models

  2025cites this paper
• Multi-Agent Fact Checking

  2025cites this paper
• Distributed Fact Checking: Learning Unreliability

  2024cites this paper
• Multi-Agent Fact-Checker: Adaptive Estimators

  2024cites this paper
• Distributed Fact Checking

  2023cites this paper
• The Identification of Discrete Mixture Models

  2023cites this paper
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity

  2023cites this paper
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures

  2022cites this paper
• A super-polynomial lower bound for learning nonparametric mixtures

  2022cites this paper
• Learning latent causal graphs via mixture oracles

  2021cites this paper
• Causal Inference Despite Limited Global Confounding via Mixture Models

  2021cites this paper