Spatio-spectral limiting on Boolean cubes. (English) Zbl 1462.94012
Summary: The operator that first truncates to a neighborhood of the origin in the spatial domain then truncates to a neighborhood of the origin in the spectral domain is investigated in the case of Boolean cubes. This operator is self adjoint on the space of functions spanned by the Laplacian eigenvectors corresponding to small eigenvalues. The eigenspaces of this iterated projection operator are studied through reduced matrices based on certain invariant subspaces. They are shown to depend fundamentally on the neighborhood structure of the cube defined in terms of Hamming distance.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A20 | Sampling theory in information and communication theory |
| 42C10 | Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) |
| 65T99 | Numerical methods in Fourier analysis |
References:
| [1] | Alon, N.; Dinur, I.; Friedgut, E.; Sudakov, B., Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal., 14, 5, 913-940 (2004) · Zbl 1056.05104 · doi:10.1007/s00039-004-0478-3 |
| [2] | Amadei, M., Manzoli, U., Merani, M.L.: On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users, Global Telecommunications Conference, 2002. GLOBECOM ’02. IEEE, vol. 1, pp. 841-845 (2002) |
| [3] | Bernasconi, A.; Codenotti, B., Spectral analysis of Boolean functions as a graph eigenvalue problem, IEEE Trans. Comput., 48, 3, 345-351 (1999) · Zbl 1391.94908 · doi:10.1109/12.755000 |
| [4] | Chen, S.; Varma, R.; Sandryhaila, A.; Kovačević, J., Discrete signal processing on graphs: sampling theory, IEEE Trans. Signal Process., 63, 24, 6510-6523 (2015) · Zbl 1395.94094 · doi:10.1109/TSP.2015.2469645 |
| [5] | de Wolf, R., A brief introduction to Fourier analysis on the Boolean cube, Theory Comput. Grad. Surv., 1, 1-20 (2008) · doi:10.4086/toc.gs.2008.001 |
| [6] | Grünbaum, FA, Eigenvectors of a Toeplitz matrix: Discrete version of the prolate spheroidal wave functions, SIAM J. Algebraic Discret. Methods, 2, 2, 136-141 (1981) · Zbl 0519.47019 · doi:10.1137/0602017 |
| [7] | Grünbaum, FA, Toeplitz matrices commuting with tridiagonal matrices, Linear Algebra Appl., 40, 25-36 (1981) · Zbl 0477.15005 · doi:10.1016/0024-3795(81)90138-5 |
| [8] | Gur, T.; Tamuz, O., Testing Booleanity and the uncertainty principle, Chic. J. Theoret. Comput. Sci., 14, 14 (2013) · Zbl 1286.68490 |
| [9] | Heil, C., What is \(\ldots\) a frame?, Notices Am. Math. Soc., 60, 6, 748-750 (2013) · Zbl 1322.42001 · doi:10.1090/noti1011 |
| [10] | Hogan, JA; Lakey, JD, Duration and Bandwidth Limiting. Prolate Functions, Sampling, and Applications (2012), Boston: Birkhäuser, Boston · Zbl 1236.94003 · doi:10.1007/978-0-8176-8307-8 |
| [11] | Hogan, JA; Lakey, JD, An analogue of Slepian vectors on Boolean hypercubes, J. Fourier Anal. Appl., 25, 4, 2004-2020 (2019) · Zbl 1416.94027 · doi:10.1007/s00041-018-09654-w |
| [12] | Hogan, J.A., Lakey, J.D.: Some invariant spaces on products of short cycles. Arxiv e-prints arXiv:2012.11752 (2020) |
| [13] | Hogan, J.A., Lakey, J.D.: Spatio-spectral limiting on redundant cubes: a case study, Excursions in Harmonic Analysis, Volume 6: In Honor of John Benedetto’s 80th Birthday (M. Hirn, S. Li, K. Okoudjou, S. Saliani, and O. Yilmaz, eds.), Springer Nature, to appear (2020) |
| [14] | Huang, Z.; Chan, NH, Walsh Fourier transform of locally stationary time series, J. Time Ser. Anal., 41, 2, 312-340 (2020) · Zbl 1444.62106 · doi:10.1111/jtsa.12509 |
| [15] | Kushilevitz, E.; Mansour, Y., Learning decision trees using the Fourier spectrum, SIAM J. Comput., 22, 6, 1331-1348 (1993) · Zbl 0799.68159 · doi:10.1137/0222080 |
| [16] | Landau, HJ; Pollak, HO, Prolate spheroidal wave functions, Fourier analysis and uncertainty. II, Bell Syst. Tech. J., 40, 65-84 (1961) · Zbl 0184.08602 · doi:10.1002/j.1538-7305.1961.tb03977.x |
| [17] | Landau, HJ; Widom, H., Eigenvalue distribution of time and frequency limiting, J. Math. Anal. Appl., 77, 469-481 (1980) · Zbl 0471.47029 · doi:10.1016/0022-247X(80)90241-3 |
| [18] | Leus, G., Segarra, S., Ribeiro, A., Marques, A.G.: The dual graph shift operator: Identifying the support of the frequency domain, Arxiv e-prints arXiv:1705.08987 (2017) |
| [19] | Linial, N.; Mansour, Y.; Nisan, N., Constant depth circuits, Fourier transform, and learnability, J. ACM, 40, 3, 607-620 (1993) · Zbl 0781.94006 · doi:10.1145/174130.174138 |
| [20] | Mitton, M., On the Walsh-Fourier analysis of Boolean functions, J. Discret. Math. Sci. Cryptogr., 9, 3, 429-439 (2006) · Zbl 1154.94014 · doi:10.1080/09720529.2006.10698089 |
| [21] | Morettin, PA, Walsh-Fourier analysis and its statistical applications: comment, J. Am. Stat. Assoc., 86, 414, 482-483 (1991) |
| [22] | Mossel, E.; O’Donnell, R., Special issue on analysis of Boolean functions: guest editors’ foreword, Theory Comput., 9, 579-585 (2013) · Zbl 1298.00169 · doi:10.4086/toc.2013.v009a016 |
| [23] | Moysiadis, T.; Fokianos, K., On locally dyadic stationary processes, IEEE Trans. Inf. Theory, 63, 8, 4829-4837 (2017) · Zbl 1372.94365 · doi:10.1109/TIT.2016.2631143 |
| [24] | O’Donnell, R., Analysis of Boolean Functions (2014), New York: Cambridge University Press, New York · Zbl 1336.94096 · doi:10.1017/CBO9781139814782 |
| [25] | Shi, J., Moura, J.M.F.: Graph signal processing: Modulation, convolution, and sampling. Arxiv preprint arXiv:1912.06762 (2019) |
| [26] | Slepian, D., Prolate spheroidal wave functions, Fourier analysis and uncertainty. IV. Extensions to many dimensions; generalized prolate spheroidal functions, Bell Syst. Tech. J., 43, 3009-3057 (1964) · Zbl 0184.08604 · doi:10.1002/j.1538-7305.1964.tb01037.x |
| [27] | Slepian, D., Prolate spheroidal wave functions, Fourier analysis, and uncertainty. V—The discrete case, Bell Syst. Tech. J., 57, 1371-1430 (1978) · Zbl 0378.33006 · doi:10.1002/j.1538-7305.1978.tb02104.x |
| [28] | Slepian, D.; Pollak, HO, Prolate spheroidal wave functions, Fourier analysis and uncertainty. I, Bell Syst. Tech. J., 40, 43-63 (1961) · Zbl 0184.08601 · doi:10.1002/j.1538-7305.1961.tb03976.x |
| [29] | Stobbe, P.; Krause, A., Learning Fourier sparse set functions, J. Mach. Learn. Res., 22, 1125-1133 (2012) |
| [30] | Stoffer, DS, Walsh-Fourier analysis and its statistical applications, J. Am. Stat. Assoc., 86, 414, 461-479 (1991) · doi:10.1080/01621459.1991.10475067 |
| [31] | Thomson, DJ, Spectrum estimation and harmonic analysis, Proc. IEEE, 70, 1055-1096 (1982) · doi:10.1109/PROC.1982.12433 |
| [32] | Tsitsvero, M.; Barbarossa, S.; Di Lorenzo, P., Signals on graphs: Uncertainty principle and sampling, IEEE Trans. Signal Process., 64, 4845-4860 (2016) · Zbl 1414.94874 · doi:10.1109/TSP.2016.2573748 |
| [33] | Wendler, C., Amrollahi, A., Seifert, B., Krause, A., Püschel, M.: Learning set functions that are sparse in non-orthogonal Fourier bases. Arxiv e-prints arXiv:2010.00439 (2020) |
| [34] | Xu, WY; Chamzas, C., On the periodic discrete prolate spheroidal sequences, SIAM J. Appl. Math., 44, 1210-1217 (1984) · Zbl 0585.65012 · doi:10.1137/0144086 |
| [35] | Zemen, T., Mecklenbräuker, C.F.: Time-variant channel estimation using discrete prolate spheroidal sequences. IEEE Trans. Signal Process. 53(9), 3597-3607 (2005) · Zbl 1370.94292 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
