Search

We study the convergence properties of gradient descent for training deep linear neural networks, i.e., deep matrix factorizations, by extending a previous analysis for the related gradient flow. We show that under suitable conditions on the step sizes gradient descent converges to a critical point of the loss function, i.e., the square loss in this article. Furthermore, we demonstrate that for almost all initializations gradient descent converges to a global minimum in the case of two layers. In the case of three or more layers we show that gradient descent converges to a global minimum on the manifold matrices of some fixed rank, where the rank cannot be determined a priori., Comment: Minor changes

We study the convergence of gradient flows related to learning deep linear neural networks (where the activation function is the identity map) from data. In this case, the composition of the network layers amounts to simply multiplying the weight matrices of all layers together, resulting in an overparameterized problem. The gradient flow with respect to these factors can be re-interpreted as a Riemannian gradient flow on the manifold of rank-$r$ matrices endowed with a suitable Riemannian metric. We show that the flow always converges to a critical point of the underlying functional. Moreover, we establish that, for almost all initializations, the flow converges to a global minimum on the manifold of rank $k$ matrices for some $k\leq r$., Comment: Minor changes; version accepted for publication in Information and Inference

The task of reconstructing a low rank matrix from incomplete linear measurements arises in areas such as machine learning, quantum state tomography and in the phase retrieval problem. In this note, we study the particular setup that the measurements are taken with respect to rank one matrices constructed from the elements of a random tight frame. We consider a convex optimization approach and show both robustness of the reconstruction with respect to noise on the measurements as well as stability with respect to passing to approximately low rank matrices. This is achieved by establishing a version of the null space property of the corresponding measurement map., Comment: 3 pages

The problem of recovering a matrix of low rank from an incomplete and possibly noisy set of linear measurements arises in a number of areas. In order to derive rigorous recovery results, the measurement map is usually modeled probabilistically. We derive sufficient conditions on the minimal amount of measurements ensuring recovery via convex optimization. We establish our results via certain properties of the null space of the measurement map. In the setting where the measurements are realized as Frobenius inner products with independent standard Gaussian random matrices we show that $10 r (n_1 + n_2)$ measurements are enough to uniformly and stably recover an $n_1 \times n_2$ matrix of rank at most $r$. We then significantly generalize this result by only requiring independent mean-zero, variance one entries with four finite moments at the cost of replacing $10$ by some universal constant. We also study the case of recovering Hermitian rank-$r$ matrices from measurement matrices proportional to rank-one projectors. For $m \geq C r n$ rank-one projective measurements onto independent standard Gaussian vectors, we show that nuclear norm minimization uniformly and stably reconstructs Hermitian rank-$r$ matrices with high probability. Next, we partially de-randomize this by establishing an analogous statement for projectors onto independent elements of a complex projective 4-designs at the cost of a slightly higher sampling rate $m \geq C rn \log n$. Moreover, if the Hermitian matrix to be recovered is known to be positive semidefinite, then we show that the nuclear norm minimization approach may be replaced by minimizing the $\ell_2$-norm of the residual subject to the positive semidefinite constraint. Then no estimate of the noise level is required a priori. We discuss applications in quantum physics and the phase retrieval problem., Comment: 26 pages

We study the recovery of Hermitian low rank matrices $X \in \mathbb{C}^{n \times n}$ from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form $a_j a_j^*$ for some measurement vectors $a_1,...,a_m$, i.e., the measurements are given by $y_j = \mathrm{tr}(X a_j a_j^*)$. The case where the matrix $X=x x^*$ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements, $y_j = |\langle x,a_j\rangle|^2$ via the PhaseLift approach, which has been introduced recently. We derive bounds for the number $m$ of measurements that guarantee successful uniform recovery of Hermitian rank $r$ matrices, either for the vectors $a_j$, $j=1,...,m$, being chosen independently at random according to a standard Gaussian distribution, or $a_j$ being sampled independently from an (approximate) complex projective $t$-design with $t=4$. In the Gaussian case, we require $m \geq C r n$ measurements, while in the case of $4$-designs we need $m \geq Cr n \log(n)$. Our results are uniform in the sense that one random choice of the measurement vectors $a_j$ guarantees recovery of all rank $r$-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate $4$-designs generalizes and improves a recent bound on phase retrieval due to Gross, Kueng and Krahmer. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii., Comment: 24 pages

We analyze the geometry of the supersingular locus of the reduction modulo p of a Shimura variety associated to a unitary similitude group GU(1,n-1) over Q, in the case that p is ramified. We define a stratification of this locus and show that its incidence complex is closely related to a certain Bruhat-Tits simplicial complex. Each stratum is isomorphic to a Deligne-Lusztig variety associated to some symplectic group over F_p and some Coxeter element. The closure of each stratum is a normal projective variety with at most isolated singularities. The results are analogous to those of Vollaard/Wedhorn in the case when p is inert., Comment: A few more corrections, to appear in Math. Zeitschrift

In this note we prove that the difference divisors associated with special cycles on unitary Rapoport-Zink spaces of signature (1,n-1) in the unramified case are always regular., Comment: 3 pages

The arithmetic fundamental lemma conjecture of the third author connects the derivative of an orbital integral on a symmetric space with an intersection number on a formal moduli space of $p$-divisible groups of Picard type. It arises in the relative trace formula approach to the arithmetic Gan-Gross-Prasad conjecture. We prove this conjecture in the minuscule case., Comment: Referee's comments incorporated; in particular, the existence of frames for using the theory of displays in the proofs of Theorems 9.4 and 9.5 is clarified. To appear in Compositio Math

We establish a close connection between intersection multiplicities of special cycles on arithmetic models of the Shimura variety for GU(1,2) and Fourier coefficients of derivatives of certain incoherent Eisenstein series, confirming a conjecture of Kudla and Rapoport. The paper is divided into two parts. The first part is the bulk of the paper and investigates intersections of local special cycles which are defined on a certain moduli space of p-divisible groups. This moduli space of p-divisible groups can be used for the uniformization of the completion of the Shimura variety along the supersingular locus in the fiber at an inert prime p. We investigate the structure of local special cycles and of their intersections. In particular, we give an explicit description of the special fiber of a local special cycle. We then prove an explicit formula for the intersection multiplicity of three local special cycles and relate it to certain hermitian representation densities, also confirming a conjecture of Kudla and Rapoport. To this end, we also give an explicit inductive formula for the relevant hermitian representation densities \alpha_p(1_s,T), where T is of the form diag(p^{a_1},...,p^{a_n}). In the second part, we apply the main result of the first part to prove the relation of intersection multiplicities of (global) special cycles and Fourier coefficients of derivatives of Eisenstein series., Comment: 42 pages

We establish a close connection between the intersection multiplicity of three arithmetic Hirzebruch-Zagier cycles and the Fourier coefficients of the derivative of a certain Siegel-Eisenstein series at its center of symmetry. Our main result proves a conjecture of Kudla and Rapoport.

We define the notion of antispecial cycles on the Drinfeld upper half plane in analogy to the notion of special cycles defined by Kudla and Rapoport in their Inventiones paper. We determine equations for antispecial cycles and calculate the intersection multiplicity of two antispecial cycles. The result is applied to calculate the intersection multiplicity of certain degenerate Hirzebruch-Zagier cycles. Finally we compare this intersection multiplicity to certain representation densities.