### On Matrix Rearrangement Inequalities

##### arXiv preprint, 2019

###### Rima Alaifari, Xiuyuan Cheng, Lillian B. Pierce, Stefan Steinerberger

Abstract. Given two symmetric and positive semidefinite square matrices , is it true that any matrix given as the product of copies of and copies of in a particular sequence must be dominated in the spectral norm by the ordered matrix product ? For example, is

Drury [10] has characterized precisely which disordered words have the property that an inequality of this type holds for all matrices . However, the -parameter family of counterexamples Drury constructs for these characterizations is comprised of matrices, and thus as stated the characterization applies only for matrices with .

In contrast, we prove that for matrices, the general rearrangement inequality holds for all disordered words. We also show that for larger matrices, the general rearrangement inequality holds for all disordered words, for most (in a sense of full measure) that are sufficiently small perturbations of the identity.

### Stability estimates for phase retrieval from discrete Gabor measurements

##### arXiv preprint, 2019

###### Rima Alaifari, Matthias Wellershoff

Abstract. Phase retrieval refers to the problem of recovering some signal (which is often modelled as an element of a Hilbert space) from phaseless measurements. It has been shown that, in the deterministic setting, phase retrieval from frame coefficients is always unstable in infinite dimensional Hilbert spaces [5] and possibly severely ill-conditioned in finite dimensional Hilbert spaces [5].

Recently, it was also shown that phase retrieval from measurements induced by the Gabor transform with Gaussian window function is stable when one is willing to accept a more relaxed semi-global stability regime [1].

We present first evidence that this semi-global stability regime allows one to do phase retrieval from measurements induced by the discrete Gabor transform in such a way that the corresponding stability constant only scales linearly in the space dimension. To this end, we utilise well-known reconstruction formulae which have been used repeatedly in recent years [4], [6-8].

### Gabor phase retrieval is severely ill-posed

##### arXiv preprint, 2018

###### Rima Alaifari, Philipp Grohs

Abstract. The problem of reconstructing a function from the magnitudes of its frame coefficients has recently been shown to be never uniformly stable in infinite-dimensional spaces [5]. This result also holds for frames that are possibly continuous [2]. On the other hand, the problem is always stable in finite-dimensional settings. A prominent example of such a phase retrieval problem is the recovery of a signal from the modulus of its Gabor transform. In this paper, we study Gabor phase retrieval and ask how the stability degrades on a natural family of finite-dimensional subspaces of the signal domain . We prove that the stability constant scales at least quadratically exponentially in the dimension of the subspaces. Our construction also shows that typical priors such as sparsity or smoothness promoting penalties do not constitute regularization terms for phase retrieval.

### ADef: an Iterative Algorithm to Construct Adversarial Deformations

##### accepted at ICLR 2019

###### Rima Alaifari, Giovanni S. Alberti, Tandri Gauksson

Abstract. While deep neural networks have proven to be a powerful tool for many recognition and classification tasks, their stability properties are still not well understood. In the past, image classifiers have been shown to be vulnerable to so-called adversarial attacks, which are created by additively perturbing the correctly classified image.

In this paper, we propose the ADef algorithm to construct a different kind of adversarial attack created by iteratively applying small deformations to the image, found through a gradient descent step. We demonstrate our results on MNIST with a convolutional neural network and on ImageNet with Inception-v3 and ResNet-101.

### Stable phase retrieval in infinite dimensions

##### accepted in Foundations of Computational Mathematics, 2018

###### Rima Alaifari, Ingrid Daubechies, Philipp Grohs, Rujie Yin

Abstract. The problem of phase retrieval is to determine a signal , with a Hilbert space, from intensity measurements

associated with a measurement system . Such problems can be seen in a wide variety of applications, ranging from X-ray crystallography, microscopy to audio processing and deep learning algorithms and accordingly, a large body of literature treating the mathematical and algorithmic solution of phase retrieval problems has emerged in recent years.

Recent work [9,3] has shown that, whenever is infinite-dimensional, phase retrieval is never uniformly stable, and that, although it is always stable in the finite dimensional setting, the stability deteriorates severely in the dimension of the problem [9]. Any finite dimensional approximation of an infinite dimensional problem has to take into account this phenomenon which makes one wonder whether phase retrieval is even advisable in these situations.

On the other hand, all observed instabilities are of a certain type: they occur whenever the function of intensity measurements is concentrated on disjoint sets , i.e., when where is concentrated on (and ). Indeed, it is easy to see that intensity measurements of any function will be close to those of while the functions themselves need not be close at all.

Motivated by these considerations we propose a new paradigm for stable phase retrieval by considering the problem of reconstructing up to a phase factor that is not global, but that can be different for each of the subsets , i.e., recovering up to the equivalence

We present concrete applications (for example in X-ray diffraction imaging or audio processing) where this new notion of stability is natural and meaningful and show that in this setting stable phase retrieval can actually be achieved, for instance if the measurement system is a Gabor frame or a frame of Cauchy wavelets.

### Phase retrieval in the general setting of continuous frames for Banach spaces

##### SIAM Math Analysis Vol. 49 Issue 3, 2017

###### Rima Alaifari, Philipp Grohs

Abstract. We develop a novel and unifying setting for phase retrieval problems that works in Banach spaces and for continuous frames and consider the questions of uniqueness and stability of the reconstruction from phaseless measurements. Our main result states that also in this framework, the problem of phase retrieval is never uniformly stable in infinite dimensions. On the other hand, we show weak stability of the problem. This complements recent work [9], where it has been shown that phase retrieval is always unstable for the setting of discrete frames in Hilbert spaces. In particular, our result implies that the stability properties cannot be improved by oversampling the underlying discrete frame.

We generalize the notion of complement property (CP) to the setting of continuous frames for Banach spaces (over or ) and verify that it is a necessary condition for uniqueness of the phase retrieval problem; when the CP is also sufficient for uniqueness. In our general setting, we also prove a conjecture posed by Bandeira et al. [5], which was originally formulated for finite-dimensional spaces: for the case the strong complement property (SCP) is a necessary condition for stability. To prove our main result, we show that the SCP can never hold for frames of infinite-dimensional Banach spaces.

### Reconstructing real-valued functions from unsigned coefficients with respect to wavelet and other frames

##### Journal of Fourier Analysis and Applications Vol. 23 Issue 6, 2017

###### Rima Alaifari, Ingrid Daubechies, Philipp Grohs, Gaurav Thakur

Abstract. In this paper we consider the following problem of phase retrieval: Given a collection of real-valued band-limited functions that constitutes a semi-discrete frame, we ask whether any real-valued function can be uniquely recovered from its unsigned convolutions .

We find that under some mild assumptions on the semi-discrete frame and if has exponential decay at , it suffices to know on suitably fine lattices to uniquely determine (up to a global sign factor).

We further establish a local stability property of our reconstruction problem. Finally, for two concrete examples of a (discrete) frame of , , we show that through sufficient oversampling one obtains a frame such that any real-valued function with exponential decay can be uniquely recovered from its unsigned frame coefficients.

### Stability estimates for the regularized inversion of the truncated Hilbert transform

##### Inverse Problems Vol. 32, 2016

###### Rima Alaifari, Michel Defrise, Alexander Katsevich

Abstract. In limited data computerized tomography, the 2D or 3D problem can be reduced to a family of 1D problems using the differentiated backprojection (DBP) method. Each 1D problem consists of recovering a compactly supported function , where is a finite interval, from its partial Hilbert transform data. When the Hilbert transform is measured on a finite interval that only overlaps but does not cover this inversion problem is known to be severely ill-posed [1]. In this paper, we study the reconstruction of restricted to the overlap region . We show that with this restriction and by assuming prior knowledge on the norm or on the variation of , better stability with Hölder continuity (typical for mildly ill-posed problems) can be obtained.

### Lower bounds for the truncated Hilbert transform

##### Revista Matemática Iberoamericana Vol. 32 Issue 1, 2016

###### Rima Alaifari, Lillian B. Pierce, Stefan Steinerberger

Abstract. Given two intervals that are either disjoint or overlap, we ask whether it is possible to reconstruct a real-valued function from knowing its Hilbert transform on . This problem has a unique answer (the nullspace is trivial) but is severely ill-posed. We isolate the difficulty and show that by restricting to functions having their variation bounded, reconstruction becomes stable. In particular, for functions , we show that

for some constants depending only on . This inequality is sharp, however, it remains an open problem whether can be replaced by .

### Asymptotic analysis of the SVD of the truncated Hilbert transform with overlap

##### SIAM Math Analysis Vol. 47 Issue 1, 2015

###### Rima Alaifari, Michel Defrise, Alexander Katsevich

Abstract. The truncated Hilbert transform with overlap is an operator that arises in tomographic reconstruction from limited data, more precisely in the method of differentiated back-projection (DBP). Recent work [1] has shown that the singular values of this operator accumulate at both zero and one. To better understand the properties of the operator and, in particular, the ill-posedness of the inverse problem associated with it, it is of interest to know the rates at which

the singular values approach zero and one. In this paper, we exploit the property that commutes with a second-order differential operator and the global asymptotic behavior of its eigenfunctions to find the asymptotics of the singular values and singular functions of .

### Spectral analysis of the truncated Hilbert transform with overlap

##### SIAM Math Analysis Vol. 46 Issue 1, 2014

###### Reema Al-Aifari, Alexander Katsevich

Abstract. We study a restriction of the Hilbert transform as an operator from to for real numbers . The operator arises in tomographic reconstruction from limited data, more precisely in the method of differentiated back-projection (DBP). There, the reconstruction requires recovering a family of one-dimensional functions supported on compact intervals from its Hilbert transform measured on intervals that might only overlap, but not cover . We show that the inversion of is ill-posed, which is why we investigate the spectral properties of . We relate the operator to a self-adjoint

*two-interval Sturm-Liouville problem*, for which we prove that the spectrum is discrete. The Sturm-Liouville operator is found to commute with , which then implies that the spectrum of is discrete. Furthermore, we express the singular value decomposition of in terms of the solutions to the Sturm-Liouville problem. The singular values of accumulate at both 0 and 1, implying that is not a compact operator. We conclude by illustrating the properties obtained for numerically.

### The continuous Procrustes distance between two surfaces

##### Communications on Pure and Applied Mathematics Vol. 66 Issue 6, 2013

###### Yaron Lipman, Reema Al-Aifari, Ingrid Daubechies

Princeton University

Abstract. The Procrustes distance is used to quantify the similarity or dissimilarity of (3-dimensional) shapes, and extensively used in biological morphometrics. Typically each (normalized) shape is represented by landmark points, chosen to be homologous, as far as possible, and the Procrustes distance is then computed as , where the minimization is over all Euclidean transformations, and the correspondences are picked in an optimal way. The discrete Procrustes distance has the drawback that each shape is represented by only a finite number of points, which may not capture all the geometric aspects of interest; a need has been expressed for alternatives that are still easy to compute. We propose in this paper the concept of

**continuous Procrustes distance**, and prove that it provides a true metric for two-dimensional surfaces embedded in three dimensions. We also propose an efficient algorithm to calculate approximations to this new distance.

Comments are closed.