Search

Recently Marcus, Spielman and Srivastava proved Weaver's ${\rm{KS}}_r$ conjecture, which gives a positive solution to the Kadison-Singer problem. Cohen and Br\"and\'en independently extended this result to obtain the arbitrary-rank version of Weaver's ${\rm{KS}}_r$ conjecture. In this paper, we present a new bound in Weaver's ${\rm{KS}}_r$ conjecture for the arbitrary-rank case. To do that, we introduce the definition of $(k,m)$-characteristic polynomials and employ it to improve the previous estimate on the largest root of the mixed characteristic polynomials. For the rank-one case, our bound agrees with the Bownik-Casazza-Marcus-Speegle's bound when $r=2$ and with the Ravichandran-Leake's bound when $r>2$. For the higher-rank case, we sharpen the previous bounds from Cohen and from Br\"and\'en .

In this paper, we focus on the nonlinear least squares: $\mbox{min}_{\mathbf{x} \in \mathbb{H}^d}\| |A\mathbf{x}|-\mathbf{b}\|$ where $A\in \mathbb{H}^{m\times d}$, $\mathbf{b} \in \mathbb{R}^m$ with $\mathbb{H} \in \{\mathbb{R},\mathbb{C} \}$ and consider the uniqueness and stability of solutions. Such problem arises, for instance, in phase retrieval and absolute value rectification neural networks. For the case where $\mathbf{b}=|A\mathbf{x}_0|$ for some $\mathbf{x}_0\in \mathbb{H}^d$, many results have been developed to characterize the uniqueness and stability of solutions. However, for the case where $\mathbf{b} \neq |A\mathbf{x}_0| $ for any $\mathbf{x}_0\in \mathbb{H}^d$, there is no existing result for it to the best of our knowledge. In this paper, we first focus on the uniqueness of solutions and show for any matrix $A\in \mathbb{H}^{m \times d}$ there always exists a vector $\mathbf{b} \in \mathbb{R}^m$ such that the solution is not unique. But, in real case, such ``bad'' vectors $\mathbf{b}$ are negligible, namely, if $\mathbf{b} \in \mathbb{R}_{+}^m$ does not lie in some measure zero set, then the solution is unique. We also present some conditions under which the solution is unique. For the stability of solutions, we prove that the solution is never uniformly stable. But if we restrict the vectors $\mathbf{b}$ to any convex set then it is stable., Comment: 22 pages

Weight decay is a simple yet powerful regularization technique that has been very widely used in training of deep neural networks (DNNs). While weight decay has attracted much attention, previous studies fail to discover some overlooked pitfalls on large gradient norms resulted by weight decay. In this paper, we discover that, weight decay can unfortunately lead to large gradient norms at the final phase (or the terminated solution) of training, which often indicates bad convergence and poor generalization. To mitigate the gradient-norm-centered pitfalls, we present the first practical scheduler for weight decay, called the Scheduled Weight Decay (SWD) method that can dynamically adjust the weight decay strength according to the gradient norm and significantly penalize large gradient norms during training. Our experiments also support that SWD indeed mitigates large gradient norms and often significantly outperforms the conventional constant weight decay strategy for Adaptive Moment Estimation (Adam)., Comment: NeurIPS 2023, 21 pages, 20 figures. Keywords: Weight Decay, Regularization, Optimization, Deep Learning

The aim of sparse phase retrieval is to recover a $k$-sparse signal $\mathbf{x}_0\in \mathbb{C}^{d}$ from quadratic measurements $|\langle \mathbf{a}_i,\mathbf{x}_0\rangle|^2$ where $\mathbf{a}_i\in \mathbb{C}^d, i=1,\ldots,m$. Noting $|\langle \mathbf{a}_i,\mathbf{x}_0\rangle|^2={\text{Tr}}(A_iX_0)$ with $A_i=\mathbf{a}_i\mathbf{a}_i^*\in \mathbb{C}^{d\times d}, X_0=\mathbf{x}_0\mathbf{x}_0^*\in \mathbb{C}^{d\times d}$, one can recast sparse phase retrieval as a problem of recovering a rank-one sparse matrix from linear measurements. Yin and Xin introduced PhaseLiftOff which presents a proxy of rank-one condition via the difference of trace and Frobenius norm. By adding sparsity penalty to PhaseLiftOff, in this paper, we present a novel model to recover sparse signals from quadratic measurements. Theoretical analysis shows that the solution to our model provides the stable recovery of $\mathbf{x}_0$ under almost optimal sampling complexity $m=O(k\log(d/k))$. The computation of our model is carried out by the difference of convex function algorithm (DCA). Numerical experiments demonstrate that our algorithm outperforms other state-of-the-art algorithms used for solving sparse phase retrieval., Comment: 23 pages, 5 figures

A finite subset $X$ on the unit sphere $\mathbb{S}^{d-1}$ is called an $s$-distance set with strength $t$ if its angle set $A(X):=\{\langle \mathbf{x},\mathbf{y}\rangle : \mathbf{x},\mathbf{y}\in X,\mathbf{x}\neq\mathbf{y} \}$ has size $s$, and $X$ is a spherical $t$-design but not a spherical $(t+1)$-design. In this paper, we consider to estimate the maximum size of such antipodal set for small $s$. First, we improve the known bound on $|X|$ for each even integer $s\in[\frac{t+5}{2}, t+1]$ when $t\geq 3$. We next focus on two special cases: $s=3,\ t=3$ and $s=4,\ t=5$. Estimating the size of $X$ for these two cases is equivalent to estimating the size of real equiangular tight frames (ETFs) and Levenstein-equality packings, respectively. We first improve the previous estimate on the size of real ETFs and Levenstein-equality packings. This in turn gives a bound on $|X|$ when $s=3,\ t=3$ and $s=4,\ t=5$, respectively., Comment: 20 pages

Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, numerical solution of symmetric positive definite linear systems and etc. In this paper, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm called universal greedy approach (UGA) for graph sparsification. For a general spectral sparsification problem, e.g., positive subset selection problem from a set of $m$ vectors from $\mathbb{R}^n$, we propose a nonnegative UGA algorithm which needs $O(mn^2+ n^3/\epsilon^2)$ time to find a $\frac{1+\epsilon/\beta}{1-\epsilon/\beta}$-spectral sparsifier with positive coefficients with sparsity $\le\lceil\frac{n}{\epsilon^2}\rceil$, where $\beta$ is the ratio between the smallest length and largest length of the vectors. The convergence of the nonnegative UGA algorithm will be established. For the graph sparsification problem, another UGA algorithm will be proposed which can output a $\frac{1+O(\epsilon)}{1-O(\epsilon)}$-spectral sparsifier with $\lceil\frac{n}{\epsilon^2}\rceil$ edges in $O(m+n^2/\epsilon^2)$ time from a graph with $m$ edges and $n$ vertices under some mild assumptions. This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for. The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear, i.e. $O(m^{1+o(1)})$ for some $o(1)=O(\frac{(\log\log(m))^{2/3}}{\log^{1/3}(m)})$. Finally, extensive experimental results, including applications to graph clustering and least squares regression, show the effectiveness of proposed approaches.

The aim of this paper is to study the matrix discrepancy problem. Assume that $\xi_1,\ldots,\xi_n$ are independent scalar random variables with finite support and $\mathbf{u}_1,\ldots,\mathbf{u}_n\in \mathbb{C}^d$. Let $\mathcal{C}_0$ be the minimal constant for which the following holds: \[ {\rm Disc}(\mathbf{u}_1\mathbf{u}_1^*,\ldots,\mathbf{u}_n\mathbf{u}_n^*; \xi_1,\ldots,\xi_n)\,\,:=\,\,\min_{\varepsilon_1\in \mathcal{S}_1,\ldots,\varepsilon_n\in \mathcal{S}_n}\bigg\|\sum_{i=1}^n\mathbb{E}[\xi_i]\mathbf{u}_i\mathbf{u}_i^*-\sum_{i=1}^n\varepsilon_i\mathbf{u}_i\mathbf{u}_i^*\bigg\|\leq \mathcal{C}_0\cdot\sigma, \] where $\sigma^2 = \big\|\sum_{i=1}^n \mathbf{Var}[\xi_i](\mathbf{u}_i\mathbf{u}_i^*)^2\big\|$ and $\mathcal{S}_j$ denotes the support of $\xi_j, j=1,\ldots,n$. Motivated by the technology developed by Bownik, Casazza, Marcus, and Speegle, we prove $\mathcal{C}_0\leq 3$. This improves Kyng, Luh and Song's method with which $\mathcal{C}_0\leq 4$. For the case where $\{\mathbf{u}_i\}_{i=1}^n\subset \mathbb{C}^d$ is a unit-norm tight frame with $ n\leq 2d-1$ and $\xi_1,\ldots,\xi_n$ are independent Rademacher random variables, we present the exact value of ${\rm Disc}(\mathbf{u}_1\mathbf{u}_1^*,\ldots,\mathbf{u}_n\mathbf{u}_n^*; \xi_1,\ldots,\xi_n)=\sqrt{\frac{n}{d}}\cdot\sigma$, which implies $\mathcal{C}_0\geq \sqrt{2}$.

The aim of noisy phase retrieval is to estimate a signal $\mathbf{x}_0\in \mathbb{C}^d$ from $m$ noisy intensity measurements $b_j=\left\lvert \langle \mathbf{a}_j,\mathbf{x}_0 \rangle \right\rvert^2+\eta_j, \; j=1,\ldots,m$, where $\mathbf{a}_j \in \mathbb{C}^d$ are known measurement vectors and $\eta=(\eta_1,\ldots,\eta_m)^\top \in \mathbb{R}^m$ is a noise vector. A commonly used model for estimating $\mathbf{x}_0$ is the intensity-based model $\widehat{\mathbf{x}}:=\mbox{argmin}_{\mathbf{x} \in \mathbb{C}^d} \sum_{j=1}^m \big(\left\lvert \langle \mathbf{a}_j,\mathbf{x} \rangle \right\rvert^2-b_j \big)^2$. Although one has already developed many efficient algorithms to solve the intensity-based model, there are very few results about its estimation performance. In this paper, we focus on the estimation performance of the intensity-based model and prove that the error bound satisfies $\min_{\theta\in \mathbb{R}}\|\widehat{\mathbf{x}}-e^{i\theta}\mathbf{x}_0\|_2 \lesssim \min\Big\{\frac{\sqrt{\|\eta\|_2}}{{m}^{1/4}}, \frac{\|\eta\|_2}{\| \mathbf{x}_0\|_2 \cdot \sqrt{m}}\Big\}$ under the assumption of $m \gtrsim d$ and $\mathbf{a}_j, j=1,\ldots,m,$ being Gaussian random vectors. We also show that the error bound is sharp. For the case where $\mathbf{x}_0$ is a $s$-sparse signal, we present a similar result under the assumption of $m \gtrsim s \log (ed/s)$. To the best of our knowledge, our results are the first theoretical guarantees for the intensity-based model and its sparse version. Our proofs employ Mendelson's small ball method which can deliver an effective lower bound on a nonnegative empirical process., Comment: 40 pages

We study the stable recovery of complex $k$-sparse signals from as few phaseless measurements as possible. The main result is to show that one can employ $\ell_1$ minimization to stably recover complex $k$-sparse signals from $m\geq O(k\log (n/k))$ complex Gaussian random quadratic measurements with high probability. To do that, we establish that Gaussian random measurements satisfy the restricted isometry property over rank-$2$ and sparse matrices with high probability. This paper presents the first theoretical estimation of the measurement number for stably recovering complex sparse signals from complex Gaussian quadratic measurements., Comment: 17 pages

The aim of generalized phase retrieval is to recover $\mathbf{x}\in \mathbb{F}^d$ from the quadratic measurements $\mathbf{x}^*A_1\mathbf{x},\ldots,\mathbf{x}^*A_N\mathbf{x}$, where $A_j\in \mathbf{H}_d(\mathbb{F})$ and $\mathbb{F}=\mathbb{R}$ or $\mathbb{C}$. In this paper, we study the matrix set $\mathcal{A}=(A_j)_{j=1}^N$ which has the almost everywhere phase retrieval property. For the case $\mathbb{F}=\mathbb{R}$, we show that $N\geq d+1$ generic matrices with prescribed ranks have almost everywhere phase retrieval property. We also extend this result to the case where $A_1,\ldots,A_N$ are orthogonal matrices and hence establish the almost everywhere phase retrieval property for the fusion frame phase retrieval. For the case where $\mathbb{F}=\mathbb{C}$, we obtain similar results under the assumption of $N\geq 2d$. We lower the measurement number $d+1$ (resp. $2d$) with showing that there exist $N=d$ (resp. $2d-1$) matrices $A_1,\ldots, A_N\in \mathbf{H}_d(\mathbb{R})$ (resp. $\mathbf{H}_d(\mathbb{C})$) which have the almost everywhere phase retrieval property. Our results are an extension of almost everywhere phase retrieval from the standard phase retrieval to the general setting and the proofs are often based on some new ideas about determinant variety., Comment: 27 pages

For any positive real number $p$, the $p$-frame potential of $N$ unit vectors $X:=\{\mathbf x_1,\ldots,\mathbf x_N\}\subset \mathbb R^d$ is defined as ${\rm FP}_{p,N,d}(X)=\sum_{i\neq j}|\langle \mathbf x_i,\mathbf x_j\rangle |^p$. In this paper, we focus on the special case $N=d+1$ and establish the unique minimizer of ${\rm FP}_{p,d+1,d}$ for $p\in (0,2)$. Our results completely solve the minimization problem of $p$-frame potential when $N=d+1$, which confirms a conjecture posed by Chen, Gonzales, Goodman, Kang and Okoudjou., Comment: 18 pages

In this paper, we propose a new non-convex algorithm for solving the phase retrieval problem, i.e., the reconstruction of a signal $ \vx\in\H^n $ ($\H=\R$ or $\C$) from phaseless samples $ b_j=\abs{\langle \va_j, \vx\rangle } $, $ j=1,\ldots,m $. The proposed algorithm solves a new proposed model, perturbed amplitude-based model, for phase retrieval and is correspondingly named as {\em Perturbed Amplitude Flow} (PAF). We prove that PAF can recover $c\vx$ ($\abs{c} = 1$) under $\mathcal{O}(n)$ Gaussian random measurements (optimal order of measurements). Starting with a designed initial point, our PAF algorithm iteratively converges to the true solution at a linear rate for both real and complex signals. Besides, PAF algorithm needn't any truncation or re-weighted procedure, so it enjoys simplicity for implementation. The effectiveness and benefit of the proposed method are validated by both the simulation studies and the experiment of recovering natural images.