Mark A. Iwen

Mark A. Iwen, Brian Preskitt, Rayan Saab et al.

We improve a phase retrieval approach that uses correlation-based measurements with compactly supported measurement masks [27]. The improved algorithm admits deterministic measurement constructions together with a robust, fast recovery algorithm that consists of solving a system of linear equations in a lifted space, followed by finding an eigenvector (e.g., via an inverse power iteration). Theoretical reconstruction error guarantees from [27] are improved as a result for the new and more robust reconstruction approach proposed herein. Numerical experiments demonstrate robustness and computational efficiency that outperforms competing approaches on large problems. Finally, we show that this approach also trivially extends to phase retrieval problems based on windowed Fourier measurements.

Alp Ozdemir, Ali Zare, Mark A. Iwen et al.

The widespread use of multisensor technology and the emergence of big datasets have created the need to develop tools to reduce, approximate, and classify large and multimodal data such as higher-order tensors. While early approaches focused on matrix and vector based methods to represent these higher-order data, more recently it has been shown that tensor decomposition methods are better equipped to capture couplings across their different modes. For these reasons, tensor decomposition methods have found applications in many different signal processing problems including dimensionality reduction, signal separation, linear regression, feature extraction, and classification. However, most of the existing tensor decomposition methods are based on the principle of finding a low-rank approximation in a linear subspace structure, where the definition of the rank may change depending on the particular decomposition. Since many datasets are not necessarily low-rank in a linear subspace, this often results in high approximation errors or low compression rates. In this paper, we introduce a new adaptive, multi-scale tensor decomposition method for higher order data inspired by hybrid linear modeling and subspace clustering techniques. In particular, we develop a multi-scale higher-order singular value decomposition (MS-HoSVD) approach where a given tensor is first permuted and then partitioned into several sub-tensors each of which can be represented as a low-rank tensor with increased representational efficiency. The proposed approach is evaluated for dimensionality reduction and classification for several different real-life tensor signals with promising results.

Mark A. Iwen, Sami Merhi, Michael Perlmutter

In this short note, we consider the worst case noise robustness of any phase retrieval algorithm which aims to reconstruct all nonvanishing vectors $\mathbf{x} \in \mathbb{C}^d$ (up to a single global phase multiple) from the magnitudes of an arbitrary collection of local correlation measurements. Examples of such measurements include both spectrogram measurements of $\mathbf{x}$ using locally supported windows and masked Fourier transform intensity measurements of $\mathbf{x}$ using bandlimited masks. As a result, the robustness results considered herein apply to a wide range of both ptychographic and Fourier ptychographic imaging scenarios. In particular, the main results imply that the accurate recovery of high-resolution images of extremely large samples using highly localized probes is likely to require an extremely large number of measurements in order to be robust to worst case measurement noise, independent of the recovery algorithm employed. Furthermore, recent pushes to achieve high-speed and high-resolution ptychographic imaging of integrated circuits for process verification and failure analysis will likely need to carefully balance probe design (e.g., their effective time-frequency support) against the total number of measurements acquired in order for their imaging techniques to be stable to measurement noise, no matter what reconstruction algorithms are applied.

Mark A. Iwen, Mark Philip Roach

Let $\mathcal{M}$ be a compact $d$-dimensional submanifold of $\mathbb{R}^N$ with reach $τ$ and volume $V_{\mathcal M}$. Fix $ε\in (0,1)$. In this paper we prove that a nonlinear function $f: \mathbb{R}^N \rightarrow \mathbb{R}^{m}$ exists with $m \leq C \left(d / ε^2 \right) \log \left(\frac{\sqrt[d]{V_{\mathcal M}}}τ \right)$ such that $$(1 - ε) \| {\bf x} - {\bf y} \|_2 \leq \left\| f({\bf x}) - f({\bf y}) \right\|_2 \leq (1 + ε) \| {\bf x} - {\bf y} \|_2$$ holds for all ${\bf x} \in \mathcal{M}$ and ${\bf y} \in \mathbb{R}^N$. In effect, $f$ not only serves as a bi-Lipschitz function from $\mathcal{M}$ into $\mathbb{R}^{m}$ with bi-Lipschitz constants close to one, but also approximately preserves all distances from points not in $\mathcal{M}$ to all points in $\mathcal{M}$ in its image. Furthermore, the proof is constructive and yields an algorithm which works well in practice. In particular, it is empirically demonstrated herein that such nonlinear functions allow for more accurate compressive nearest neighbor classification than standard linear Johnson-Lindenstrauss embeddings do in practice.

Mark A. Iwen, Benjamin Schmidt, Arman Tavakoli

Let $\mathcal{M}$ be a smooth $d$-dimensional submanifold of $\mathbb{R}^N$ with boundary that's equipped with the Euclidean (chordal) metric, and choose $m \leq N$. In this paper we consider the probability that a random matrix $A \in \mathbb{R}^{m \times N}$ will serve as a bi-Lipschitz function $A: \mathcal{M} \rightarrow \mathbb{R}^m$ with bi-Lipschitz constants close to one for three different types of distributions on the $m \times N$ matrices $A$, including two whose realizations are guaranteed to have fast matrix-vector multiplies. In doing so we generalize prior randomized metric space embedding results of this type for submanifolds of $\mathbb{R}^N$ by allowing for the presence of boundary while also retaining, and in some cases improving, prior lower bounds on the achievable embedding dimensions $m$ for which one can expect small distortion with high probability. In particular, motivated by recent modewise embedding constructions for tensor data, herein we present a new class of highly structured distributions on matrices which outperform prior structured matrix distributions for embedding sufficiently low-dimensional submanifolds of $\mathbb{R}^N$ (with $d \lesssim \sqrt{N}$) with respect to both achievable embedding dimension, and computationally efficient realizations. As a consequence we are able to present, for example, a general new class of Johnson-Lindenstrauss embedding matrices for $\mathcal{O}(\log^c N)$-dimensional submanifolds of $\mathbb{R}^N$ which enjoy $\mathcal{O}(N \log (\log N))$-time matrix vector multiplications.

Sami Merhi, Ruochuan Zhang, Mark A. Iwen et al.

In this paper we consider Sparse Fourier Transform (SFT) algorithms for approximately computing the best $s$-term approximation of the Discrete Fourier Transform (DFT) $\mathbf{\hat{f}} \in \mathbb{C}^N$ of any given input vector $\mathbf{f} \in \mathbb{C}^N$ in just $\left( s \log N\right)^{\mathcal{O}(1)}$-time using only a similarly small number of entries of $\mathbf{f}$. In particular, we present a deterministic SFT algorithm which is guaranteed to always recover a near best $s$-term approximation of the DFT of any given input vector $\mathbf{f} \in \mathbb{C}^N$ in $\mathcal{O} \left( s^2 \log ^{\frac{11}{2}} (N) \right)$-time. Unlike previous deterministic results of this kind, our deterministic result holds for both arbitrary vectors $\mathbf{f} \in \mathbb{C}^N$ and vector lengths $N$. In addition to these deterministic SFT results, we also develop several new publicly available randomized SFT implementations for approximately computing $\mathbf{\hat{f}}$ from $\mathbf{f}$ using the same general techniques. The best of these new implementations is shown to outperform existing discrete sparse Fourier transform methods with respect to both runtime and noise robustness for large vector lengths $N$.