A Note on Functions Governed By Walsh Expressions

Craig Gotsman

doi:10.1109/18.79935

A Note on Functions Governed By Walsh Expressions

Research output: Contribution to journal › Article › peer-review

Abstract

Let f: {+ 1, - 1}ⁿ → 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 language	English (US)
Pages (from-to)	694-695
Number of pages	2
Journal	IEEE Transactions on Information Theory
Volume	37
Issue number	3
DOIs	https://doi.org/10.1109/18.79935
State	Published - May 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Boltzmann machine
Hadamard transform
Walsh

Access to Document

10.1109/18.79935

Cite this

@article{cfd92014153042658be92818d09f4ab2,

title = "A Note on Functions Governed By Walsh Expressions",

abstract = "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.",

keywords = "Boltzmann machine, Hadamard transform, Walsh",

author = "Craig Gotsman",

note = "Funding Information: Manuscript received March 30, 1990; revised September 17, 1990. This work was supported in part by an Eshkol fellowship, administered by the National Council for R&D, Israel Ministry of Science. C, Gotsman is with the Department of Computer Science, The Hebrew University, Jerusalem 91904, Israel. IEEE Log Number 9041982. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.",

year = "1991",

month = may,

doi = "10.1109/18.79935",

language = "English (US)",

volume = "37",

pages = "694--695",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - A Note on Functions Governed By Walsh Expressions

AU - Gotsman, Craig

N1 - Funding Information: Manuscript received March 30, 1990; revised September 17, 1990. This work was supported in part by an Eshkol fellowship, administered by the National Council for R&D, Israel Ministry of Science. C, Gotsman is with the Department of Computer Science, The Hebrew University, Jerusalem 91904, Israel. IEEE Log Number 9041982. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.

PY - 1991/5

Y1 - 1991/5

N2 - 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.

AB - 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.

KW - Boltzmann machine

KW - Hadamard transform

KW - Walsh

UR - http://www.scopus.com/inward/record.url?scp=0026154987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026154987&partnerID=8YFLogxK

U2 - 10.1109/18.79935

DO - 10.1109/18.79935

M3 - Article

AN - SCOPUS:0026154987

SN - 0018-9448

VL - 37

SP - 694

EP - 695

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 3

ER -

A Note on Functions Governed By Walsh Expressions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this