Search

Practical applications of compressed sensing often restrict the choice of its two main ingredients. They may (i) prescribe using particular redundant dictionaries for certain classes of signals to become sparsely represented, or (ii) dictate specific measurement mechanisms which exploit certain physical principles. On the problem of RIP measurement matrix design in compressed sensing with redundant dictionaries, we give a simple construction to derive sensing matrices whose compositions with a prescribed dictionary have a high probability of the RIP in the $k \log(n/k)$ regime. Our construction thus provides recovery guarantees usually only attainable for sensing matrices from random ensembles with sparsifying orthonormal bases. Moreover, we use the dictionary factorization idea that our construction rests on in the application of magnetic resonance imaging, in which also the sensing matrix is prescribed by quantum mechanical principles. We propose a recovery algorithm based on transforming the acquired measurements such that the compressed sensing theory for RIP embeddings can be utilized to recover wavelet coefficients of the target image, and show its performance on examples from the fastMRI dataset.

Die analysis is an essential numismatic method, and an important tool of ancient economic history. Yet, manual die studies are too labor-intensive to comprehensively study large coinages such as those of the Roman Empire. We address this problem by proposing a model for unsupervised computational die analysis, which can reduce the time investment necessary for large-scale die studies by several orders of magnitude, in many cases from years to weeks. From a computer vision viewpoint, die studies present a challenging unsupervised clustering problem, because they involve an unknown and large number of highly similar semantic classes of imbalanced sizes. We address these issues through determining dissimilarities between coin faces derived from specifically devised Gaussian process-based keypoint features in a Bayesian distance clustering framework. The efficacy of our method is demonstrated through an analysis of 1135 Roman silver coins struck between 64-66 C.E..

Clustering in high-dimensions poses many statistical challenges. While traditional distance-based clustering methods are computationally feasible, they lack probabilistic interpretation and rely on heuristics for estimation of the number of clusters. On the other hand, probabilistic model-based clustering techniques often fail to scale and devising algorithms that are able to effectively explore the posterior space is an open problem. Based on recent developments in Bayesian distance-based clustering, we propose a hybrid solution that entails defining a likelihood on pairwise distances between observations. The novelty of the approach consists in including both cohesion and repulsion terms in the likelihood, which allows for cluster identifiability. This implies that clusters are composed of objects which have small "dissimilarities" among themselves (cohesion) and similar dissimilarities to observations in other clusters (repulsion). We show how this modelling strategy has interesting connection with existing proposals in the literature as well as a decision-theoretic interpretation. The proposed method is computationally efficient and applicable to a wide variety of scenarios. We demonstrate the approach in a simulation study and an application in digital numismatics., Comment: 1 supplementary PDF attached. To view the supplementary PDF, please download the attachment under "Ancilliary Files"

We consider deep feedforward neural networks with rectified linear units from a signal processing perspective. In this view, such representations mark the transition from using a single (data-driven) linear representation to utilizing a large collection of affine linear representations tailored to particular regions of the signal space. This paper provides a precise description of the individual affine linear representations and corresponding domain regions that the (data-driven) neural network associates to each signal of the input space. In particular, we describe atomic decompositions of the representations and, based on estimating their Lipschitz regularity, suggest some conditions that can stabilize learning independent of the network depth. Such an analysis may promote further theoretical insight from both the signal processing and machine learning communities.

Spectral Tetris has proved to be a powerful tool for constructing sparse equal norm Hilbert space frames. We introduce a new form of Spectral Tetris which works for non-equal norm frames. It is known that this method cannot construct all frames --- even in the new case introduced here. Until now, it has been a mystery as to why Spectral Tetris sometimes works and sometimes fails. We will give a complete answer to this mystery by giving necessary and sufficient conditions for Spectral Tetris to construct frames in all cases including equal norm frames, prescribed norm frames, frames with constant spectrum of the frame operator, and frames with prescribed spectrum for the frame operator. We present a variety of examples as well as special cases where Spectral Tetris always works., Comment: 17 pages

Spectral tetris is a fexible and elementary method to construct unit norm frames with a given frame operator, having all of its eigenvalues greater than or equal to two. One important application of spectral tetris is the construction of fusion frames. We first show how the assumption on the spectrum of the frame operator can be dropped and extend the spectral tetris algorithm to construct unit norm frames with any given spectrum of the frame operator. We then provide a suffcient condition for using this generalization of spectral tetris to construct fusion frames with prescribed spectrum for the fusion frame operator and with prescribed dimensions for the subspaces. This condition is shown to be necessary in the tight case of redundancy greater than two.

Frames have established themselves as a means to derive redundant, yet stable decompositions of a signal for analysis or transmission, while also promoting sparse expansions. However, when the signal dimension is large, the computation of the frame measurements of a signal typically requires a large number of additions and multiplications, and this makes a frame decomposition intractable in applications with limited computing budget. To address this problem, in this paper, we focus on frames in finite-dimensional Hilbert spaces and introduce sparsity for such frames as a new paradigm. In our terminology, a sparse frame is a frame whose elements have a sparse representation in an orthonormal basis, thereby enabling low-complexity frame decompositions. To introduce a precise meaning of optimality, we take the sum of the numbers of vectors needed of this orthonormal basis when expanding each frame vector as sparsity measure. We then analyze the recently introduced algorithm Spectral Tetris for construction of unit norm tight frames and prove that the tight frames generated by this algorithm are in fact optimally sparse with respect to the standard unit vector basis. Finally, we show that even the generalization of Spectral Tetris for the construction of unit norm frames associated with a given frame operator produces optimally sparse frames.

Bodmann, Casazza and Kutyniok introduced a quantitative notion of redundancy for finite frames - which they called {\em upper and lower redundancies} - that match better with an intuitive understanding of redundancy for finite frames in a Hilbert space. The objective of this paper is to see how much of this theory generalizes to infinite frames.

Fusion frame theory is an emerging mathematical theory that provides a natural framework for performing hierarchical data processing. A fusion frame is a frame-like collection of subspaces in a Hilbert space, thereby generalizing the concept of a frame for signal representation. In this paper, we study the existence and construction of fusion frames. We first present a complete characterization of a special class of fusion frames, called Parseval fusion frames. The value of Parseval fusion frames is that the inverse fusion frame operator is equal to the identity and therefore signal reconstruction can be performed with minimal complexity. We then introduce two general methods -- the spatial complement and the Naimark complement -- for constructing a new fusion frame from a given fusion frame. We then establish existence conditions for fusion frames with desired properties. In particular, we address the following question: Given $M, N, m \in \NN$ and $\{\lambda_j\}_{j=1}^M$, does there exist a fusion frame in $\RR^M$ with $N$ subspaces of dimension $m$ for which $\{\lambda_j\}_{j=1}^M$ are the eigenvalues of the associated fusion frame operator? We address this problem by providing an algorithm which computes such a fusion frame for almost any collection of parameters $M, N, m \in \NN$ and $\{\lambda_j\}_{j=1}^M$. Moreover, we show how this procedure can be applied, if subspaces are to be added to a given fusion frame to force it to become Parseval., Comment: 24 pages