Last week, I attended this workshop at Oberwolfach. The weather was great, and I was rather impressed by the quality of the talks. Throughout the workshop, I paid special attention to the various problems that different people are thinking about. In what follows, I briefly discuss several of these problems.
Continue reading Applied Harmonic Analysis and Sparse Approximation
Jesse Peterson and I recently arxiv’d our paper for Wavelets and Sparsity XVI at SPIE this year. This paper focuses on learning functions of the form
where is small, , and . Notice that any such Boolean function can be viewed as a labeling function of strings of bits, and so learning the function from labeled instances amounts to a binary classification problem.
If we identify with , then the ‘s are essentially the big entries of the Walsh–Hadamard transform of , and these entries are indexed by the ‘s. As such, functions of the form are essentially the Boolean functions of concentrated spectra. These functions have been shown to well approximate the Boolean functions with sufficiently simple circuit implementations (e.g., see one, two, three), and given the strong resemblance between Boolean circuits and neural networks, the following hypothesis seems plausible:
Continue reading A relaxation of deep learning?
Back in May, I attended this year’s SampTA at American University. I spoke in a special session on phase retrieval, and as luck would have it, Cynthia Vinzant spoke in the same session about her recent solution of the 4M-4 conjecture. As you might expect, I took a moment during my talk to present the award I promised for the solution:
Recall that Cynthia (and coauthors) first proved part (a) of the conjecture, and then recently disproved part (b). During her talk, she also provided a refinement of part (b). Before stating the conjecture, recall that injectivity of the mapping is a property of the column space .
Continue reading Conjectures from SampTA
I’ve been pretty busy lately with writing and researching with visitors. These announcements serve as a quick summary of what I’ve been up to:
1. Tables of the existence of equiangular tight frames (with Matthew Fickus). Today, there’s quite a bit known about equiangular tight frames (ETFs), but what is known seems to be scattered across different papers. This paper surveys everything that is known, and tabulates all of the known real and complex ETFs with sufficiently few vectors in sufficiently small dimension. The tables were generated by coding up existence theorems in MATLAB so as to minimize errors. This serves as a “solution” to problem 21 in this documentation of the open problems discussed at the AIM workshop Frame theory intersects geometry. Recently, Matt and I have made a few ETF discoveries with John and Jesse, so you can expect this table to be updated after we announce these discoveries in the coming months.
Continue reading Three Paper Announcements
I recently finished Nate Silver‘s famous book. Some parts were more fun to read than others, but overall, it was worth the read. I was impressed by Nate’s apparently vast perspective, and he did a good job of pointing out how bad we are at predicting certain things (and explaining some of the bottlenecks).
Based on the reading, here’s a brief list of stars that need to align in order to succeed at prediction:
Continue reading The Signal and the Noise