A Note on Functions Governed By Walsh Expressions

Research output: Contribution to journalArticlepeer-review


Let f: {+ 1, - 1}n → R be a real function on the n-dimensional hypercube such that f= g(H), where g is monotonic and H is a linear combination of Walsh functions of degree ≤ d. We prove that f is determined uniquely by its Walsh-Hadamard coefficients of degree ≤ d. This generalizes a result of Bruck [2] on boolean functions on the hypercube. We apply this to show that a dth order Boltzmann machine without hidden units cannot capture correlations of degree > d.

Original languageEnglish (US)
Pages (from-to)694-695
Number of pages2
JournalIEEE Transactions on Information Theory
Issue number3
StatePublished - May 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Boltzmann machine
  • Hadamard transform
  • Walsh


Dive into the research topics of 'A Note on Functions Governed By Walsh Expressions'. Together they form a unique fingerprint.

Cite this