Search

Cavity optomechanical systems have enabled precision sensing of magnetic fields, by leveraging the optical resonance-enhanced readout and mechanical resonance-enhanced response. Previous studies have successfully achieved scalable and reproducible microcavity optomechanical magnetometry (MCOM) by incorporating Terfenol-D thin films into high-quality ($Q$) factor whispering gallery mode (WGM) microcavities. However, the sensitivity was limited to 585 pT/Hz$^{1/2}$, over 20 times inferior to those using Terfenol-D particles. In this work, we propose and demonstrate a high-sensitivity and scalable MCOM approach by sputtering a FeGaB thin film onto a high-$Q$ SiO$_2$ WGM microdisk. Theoretical studies are conducted to explore the magnetic actuation constant and noise-limited sensitivity by varying the parameters of the FeGaB film and SiO$_2$ microdisk. Multiple magnetometers with different radii are fabricated and characterized. By utilizing a microdisk with a radius of 355 $\mu$m and a thickness of 1 $\mu$m, along with a FeGaB film with a radius of 330 $\mu$m and a thickness of 1.3 $\mu$m, we have achieved a remarkable peak sensitivity of 1.68 pT/Hz$^{1/2}$ at 9.52 MHz. This represents a significant improvement of over two orders of magnitude compared with previous studies employing sputtered Terfenol-D film. Notably, the magnetometer operates without a bias magnetic field, thanks to the remarkable soft magnetic properties of the FeGaB film. Furthermore, as a proof-of-concept, we have demonstrated the real-time measurement of a pulsed magnetic field simulating the corona current in a high-voltage transmission line using our developed magnetometer. These high-sensitivity magnetometers hold great potential for various applications, such as magnetic induction tomography and corona current monitoring.

Efficiently learning equilibria with large state and action spaces in general-sum Markov games while overcoming the curse of multi-agency is a challenging problem. Recent works have attempted to solve this problem by employing independent linear function classes to approximate the marginal $Q$-value for each agent. However, existing sample complexity bounds under such a framework have a suboptimal dependency on the desired accuracy $\varepsilon$ or the action space. In this work, we introduce a new algorithm, Lin-Confident-FTRL, for learning coarse correlated equilibria (CCE) with local access to the simulator, i.e., one can interact with the underlying environment on the visited states. Up to a logarithmic dependence on the size of the state space, Lin-Confident-FTRL learns $\epsilon$-CCE with a provable optimal accuracy bound $O(\epsilon^{-2})$ and gets rids of the linear dependency on the action space, while scaling polynomially with relevant problem parameters (such as the number of agents and time horizon). Moreover, our analysis of Linear-Confident-FTRL generalizes the virtual policy iteration technique in the single-agent local planning literature, which yields a new computationally efficient algorithm with a tighter sample complexity bound when assuming random access to the simulator., Comment: Accepted at the 27th International Conference on Artificial Intelligence and Statistics (AISTATS 2024)

This paper delves into the spectral norm aspect of the Generalized Column and Row Subset Selection (GCRSS) problem. Given a target matrix $\mathbf{A}$, the objective of GCRSS is to select a column submatrix $\mathbf{B}_{:,S}$ from the source matrix $\mathbf{B}$ and a row submatrix $\mathbf{C}_{R,:}$ from the source maitrx $\mathbf{C}$, with the aim of minimizing the spectral norm of the residual matrix $(\mathbf{I}_n-\mathbf{B}_{:,S}\mathbf{B}_{:,S}^{\dagger})\mathbf{A}(\mathbf{I}_d-\mathbf{C}_{R,:}^{\dagger} \mathbf{C}_{R,:})$. By employing the interlacing polynomials method, we show that the largest root of the expected characteristic polynomial of the residual matrix serves as an upper bound on the smallest spectral norm of the residual matrix. We estimate this root for two specific GCRSS scenarios, one where $r=0$, simplifying the problem to the Generalized Column Subset Selection (GCSS) problem, and the other where $\mathbf{B}=\mathbf{C}=\mathbf{I}_d$, reducing the problem to the submatrix selection problem. In the GCSS scenario, we connect the expected characteristic polynomials to the convolution of multi-affine polynomials, leading to the derivation of the first provable reconstruction bound on the spectral norm of the residual matrix for the GCSS problem. In the submatrix selection scenario, we show that for any sufficiently small $\varepsilon>0$ and any square matrix $\mathbf{A}\in\mathbb{R}^{d\times d}$, there exist two subsets $S\subset [d]$ and $R\subset [d]$ of sizes $O(d\cdot \varepsilon^2)$ such that $\Vert\mathbf{A}_{S,R}\Vert_2\leq \varepsilon\cdot \Vert\mathbf{A}\Vert_2$. Unlike previous studies that have produced comparable results for very special cases where the matrix is either a zero-diagonal or a positive semidefinite matrix, our results apply universally to any matrix $\mathbf{A}$.

Radiation therapy (RT) aims to deliver tumoricidal doses with minimal radiation-induced normal-tissue toxicity. Compared to conventional RT (of conventional dose rate), FLASH-RT (of ultra-high dose rate) can provide additional normal tissue sparing, which however has created a new nonconvex and nonsmooth optimization problem that is highly challenging to solve. In this paper, we propose a stochastic three-operator splitting (STOS) algorithm to address the FLASH optimization problem. We establish the convergence and convergence rates of the STOS algorithm under the nonconvex framework for both unbiased gradient estimators and variance-reduced gradient estimators. These stochastic gradient estimators include the most popular ones, such as SGD, SAGA, SARAH, and SVRG, among others. The effectiveness of the STOS algorithm is validated using FLASH radiotherapy planning for patients.

We study the sparse phase retrieval problem, which seeks to recover a sparse signal from a limited set of magnitude-only measurements. In contrast to prevalent sparse phase retrieval algorithms that primarily use first-order methods, we propose an innovative second-order algorithm that employs a Newton-type method with hard thresholding. This algorithm overcomes the linear convergence limitations of first-order methods while preserving their hallmark per-iteration computational efficiency. We provide theoretical guarantees that our algorithm converges to the $s$-sparse ground truth signal $\mathbf{x}^{\natural} \in \mathbb{R}^n$ (up to a global sign) at a quadratic convergence rate after at most $O(\log (\Vert\mathbf{x}^{\natural} \Vert /x_{\min}^{\natural}))$ iterations, using $\Omega(s^2\log n)$ Gaussian random samples. Numerical experiments show that our algorithm achieves a significantly faster convergence rate than state-of-the-art methods.

In recent years, patch-based image restoration approaches have demonstrated superior performance compared to conventional variational methods. This paper delves into the mathematical foundations underlying patch-based image restoration methods, with a specific focus on establishing restoration guarantees for patch-based image inpainting, leveraging the assumption of self-similarity among patches. To accomplish this, we present a reformulation of the image inpainting problem as structured low-rank matrix completion, accomplished by grouping image patches with potential overlaps. By making certain incoherence assumptions, we establish a restoration guarantee, given that the number of samples exceeds the order of $rlog^2(N)$, where $N\times N$ denotes the size of the image and $r > 0$ represents the sum of ranks for each group of image patches. Through our rigorous mathematical analysis, we provide valuable insights into the theoretical foundations of patch-based image restoration methods, shedding light on their efficacy and offering guidelines for practical implementation.

In this paper, we investigate a category of constrained fractional optimization problems that emerge in various practical applications. The objective function for this category is characterized by the ratio of a numerator and denominator, both being convex, semi-algebraic, Lipschitz continuous, and differentiable with Lipschitz continuous gradients over the constraint sets. The constrained sets associated with these problems are closed, convex, and semi-algebraic. We propose an efficient algorithm that is inspired by the proximal gradient method, and we provide a thorough convergence analysis. Our algorithm offers several benefits compared to existing methods. It requires only a single proximal gradient operation per iteration, thus avoiding the complicated inner-loop concave maximization usually required. Additionally, our method converges to a critical point without the typical need for a nonnegative numerator, and this critical point becomes a globally optimal solution with an appropriate condition. Our approach is adaptable to unbounded constraint sets as well. Therefore, our approach is viable for many more practical models. Numerical experiments show that our method not only reliably reaches ground-truth solutions in some model problems but also outperforms several existing methods in maximizing the Sharpe ratio with real-world financial data., Comment: 29 pages, 2 figures

We investigate a generalized framework for estimating latent low-rank tensors in an online setting, encompassing both linear and generalized linear models. This framework offers a flexible approach for handling continuous or categorical variables. Additionally, we investigate two specific applications: online tensor completion and online binary tensor learning. To address these challenges, we propose the online Riemannian gradient descent algorithm, which demonstrates linear convergence and the ability to recover the low-rank component under appropriate conditions in all applications. Furthermore, we establish a precise entry-wise error bound for online tensor completion. Notably, our work represents the first attempt to incorporate noise in the online low-rank tensor recovery task. Intriguingly, we observe a surprising trade-off between computational and statistical aspects in the presence of noise. Increasing the step size accelerates convergence but leads to higher statistical error, whereas a smaller step size yields a statistically optimal estimator at the expense of slower convergence. Moreover, we conduct regret analysis for online tensor regression. Under the fixed step size regime, a fascinating trilemma concerning the convergence rate, statistical error rate, and regret is observed. With an optimal choice of step size we achieve an optimal regret of $O(\sqrt{T})$. Furthermore, we extend our analysis to the adaptive setting where the horizon T is unknown. In this case, we demonstrate that by employing different step sizes, we can attain a statistically optimal error rate along with a regret of $O(\log T)$. To validate our theoretical claims, we provide numerical results that corroborate our findings and support our assertions.

High-dimensional linear regression under heavy-tailed noise or outlier corruption is challenging, both computationally and statistically. Convex approaches have been proven statistically optimal but suffer from high computational costs, especially since the robust loss functions are usually non-smooth. More recently, computationally fast non-convex approaches via sub-gradient descent are proposed, which, unfortunately, fail to deliver a statistically consistent estimator even under sub-Gaussian noise. In this paper, we introduce a projected sub-gradient descent algorithm for both the sparse linear regression and low-rank linear regression problems. The algorithm is not only computationally efficient with linear convergence but also statistically optimal, be the noise Gaussian or heavy-tailed with a finite 1 + epsilon moment. The convergence theory is established for a general framework and its specific applications to absolute loss, Huber loss and quantile loss are investigated. Compared with existing non-convex methods, ours reveals a surprising phenomenon of two-phase convergence. In phase one, the algorithm behaves as in typical non-smooth optimization that requires gradually decaying stepsizes. However, phase one only delivers a statistically sub-optimal estimator, which is already observed in the existing literature. Interestingly, during phase two, the algorithm converges linearly as if minimizing a smooth and strongly convex objective function, and thus a constant stepsize suffices. Underlying the phase-two convergence is the smoothing effect of random noise to the non-smooth robust losses in an area close but not too close to the truth. Numerical simulations confirm our theoretical discovery and showcase the superiority of our algorithm over prior methods., Comment: This manuscript supersedes an earlier one (arXiv:2203.00953). Two manuscripts share around 60% contents. There will be no further update for the earlier manuscript

The low-rank matrix recovery problem often arises in various fields, including signal processing, machine learning, and imaging science. The Riemannian gradient descent (RGD) algorithm has proven to be an efficient algorithm for solving this problem. In this paper, we present a preconditioned Riemannian gradient descent (PRGD) for low-rank matrix recovery. The preconditioner, noted for its simplicity and computational efficiency, is constructed by weighting the (i,j)-th entry of the gradient matrix according to the norms of the i-th row and the j-th column. We establish the theoretical recovery guarantee for PRGD under the restricted isometry property assumption. Experimental results indicate that PRGD can accelerate RGD by up to tenfold in solving low-rank matrix recovery problems such as matrix completion.

This paper investigates the spectral norm version of the column subset selection problem. Given a matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ and a positive integer $k\leq\text{rank}(\mathbf{A})$, the objective is to select exactly $k$ columns of $\mathbf{A}$ that minimize the spectral norm of the residual matrix after projecting $\mathbf{A}$ onto the space spanned by the selected columns. We use the method of interlacing polynomials introduced by Marcus-Spielman-Srivastava to derive a new upper bound on the minimal approximation error. This new bound is asymptotically sharp when the matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ obeys a spectral power-law decay. The relevant expected characteristic polynomials can be written as an extension of the expected polynomial for the restricted invertibility problem, incorporating two extra variable substitution operators. Finally, we propose a deterministic polynomial-time algorithm that achieves this error bound up to a computational error.

We study the sparse phase retrieval problem, recovering an $s$-sparse length-$n$ signal from $m$ magnitude-only measurements. Two-stage non-convex approaches have drawn much attention in recent studies for this problem. Despite non-convexity, many two-stage algorithms provably converge to the underlying solution linearly when appropriately initialized. However, in terms of sample complexity, the bottleneck of those algorithms often comes from the initialization stage. Although the refinement stage usually needs only $m=\Omega(s\log n)$ measurements, the widely used spectral initialization in the initialization stage requires $m=\Omega(s^2\log n)$ measurements to produce a desired initial guess, which causes the total sample complexity order-wisely more than necessary. To reduce the number of measurements, we propose a truncated power method to replace the spectral initialization for non-convex sparse phase retrieval algorithms. We prove that $m=\Omega(\bar{s} s\log n)$ measurements, where $\bar{s}$ is the stable sparsity of the underlying signal, are sufficient to produce a desired initial guess. When the underlying signal contains only very few significant components, the sample complexity of the proposed algorithm is $m=\Omega(s\log n)$ and optimal. Numerical experiments illustrate that the proposed method is more sample-efficient than state-of-the-art algorithms.

The recovery of an unknown density matrix of large size requires huge computational resources. The recent Factored Gradient Descent (FGD) algorithm and its variants achieved state-of-the-art performance since they could mitigate the dimensionality barrier by utilizing some of the underlying structures of the density matrix. Despite their theoretical guarantee of a linear convergence rate, the convergence in practical scenarios is still slow because the contracting factor of the FGD algorithms depends on the condition number $\kappa$ of the ground truth state. Consequently, the total number of iterations can be as large as $O(\sqrt{\kappa}\ln(\frac{1}{\varepsilon}))$ to achieve the estimation error $\varepsilon$. In this work, we derive a quantum state tomography scheme that improves the dependence on $\kappa$ to the logarithmic scale; namely, our algorithm could achieve the approximation error $\varepsilon$ in $O(\ln(\frac{1}{\kappa\varepsilon}))$ steps. The improvement comes from the application of the non-convex Riemannian gradient descent (RGD). The contracting factor in our approach is thus a universal constant that is independent of the given state. Our theoretical results of extremely fast convergence and nearly optimal error bounds are corroborated by numerical results., Comment: Comments are welcome!

This paper investigates the low-rank tensor completion problem, which is about recovering a tensor from partially observed entries. We consider this problem in the tensor train format and extend the preconditioned metric from the matrix case to the tensor case. The first-order and second-order quotient geometry of the manifold of fixed tensor train rank tensors under this metric is studied in detail. Algorithms, including Riemannian gradient descent, Riemannian conjugate gradient, and Riemannian Gauss-Newton, have been proposed for the tensor completion problem based on the quotient geometry. It has also been shown that the Riemannian Gauss-Newton method on the quotient geometry is equivalent to the Riemannian Gauss-Newton method on the embedded geometry with a specific retraction. Empirical evaluations on random instances as well as on function-related tensors show that the proposed algorithms are competitive with other existing algorithms in terms of recovery ability, convergence performance, and reconstruction quality., Comment: The manuscript has been adjusted in several places

In this paper, we analyze the error estimate of a wavelet frame based image restoration method from degraded and incomplete measurements. We present the error between the underlying original discrete image and the approximate solution which has the minimal $\ell_1$-norm of the canonical wavelet frame coefficients among all possible solutions. Then we further connect the error estimate for the discrete model to the approximation to the underlying function from which the underlying image comes., Comment: arXiv admin note: text overlap with arXiv:2207.07473

The finite-rate-of-innovation (FRI) framework which corresponds a signal/image to a structured low-rank matrix is emerging as an alternative to the traditional sparse regularization. This is because such an off-the-grid approach is able to alleviate the basis mismatch between the true support in the continuous domain and the discrete grid. In this paper, we propose a two-stage off-the-grid regularization model for the image restoration. Given that the discontinuities/edges of the image lie in the zero level set of a band-limited periodic function, we can derive that the Fourier samples of the gradient of the image satisfy an annihilation relation, resulting in a low-rank two-fold Hankel matrix. In addition, since the singular value decomposition of a low-rank Hankel matrix corresponds to an adaptive tight frame system which can represent the image with sparse canonical coefficients, our approach consists of the following two stages. The first stage learns the tight wavelet frame system from a given measurement, and the second stage restores the image via the analysis approach based sparse regularization. The numerical results are presented to demonstrate that the proposed approach is compared favorably against several popular discrete regularization approaches and structured low-rank matrix approaches., Comment: arXiv admin note: text overlap with arXiv:2012.06827

Total variation (TV) minimization is one of the most important techniques in modern signal/image processing, and has wide range of applications. While there are numerous recent works on the restoration guarantee of the TV minimization in the framework of compressed sensing, there are few works on the restoration guarantee of the restoration from partial observations. This paper is to analyze the error of TV based restoration from random entrywise samples. In particular, we estimate the error between the underlying original data and the approximate solution that interpolates (or approximates with an error bound depending on the noise level) the given data that has the minimal TV seminorm among all possible solutions. Finally, we further connect the error estimate for the discrete model to the sparse gradient restoration problem and to the approximation to the underlying function from which the underlying true data comes.

The phase retrieval problem is concerned with recovering an unknown signal $\bf{x} \in \mathbb{R}^n$ from a set of magnitude-only measurements $y_j=|\langle \bf{a}_j,\bf{x} \rangle|, \; j=1,\ldots,m$. A natural least squares formulation can be used to solve this problem efficiently even with random initialization, despite its non-convexity of the loss function. One way to explain this surprising phenomenon is the benign geometric landscape: (1) all local minimizers are global; and (2) the objective function has a negative curvature around each saddle point and local maximizer. In this paper, we show that $m=O(n \log n)$ Gaussian random measurements are sufficient to guarantee the loss function of a commonly used estimator has such benign geometric landscape with high probability. This is a step toward answering the open problem given by Sun-Qu-Wright, in which the authors suggest that $O(n \log n)$ or even $O(n)$ is enough to guarantee the favorable geometric property., Comment: 32 pages

We study the robust matrix completion problem for the low-rank Hankel matrix, which detects the sparse corruptions caused by extreme outliers while we try to recover the original Hankel matrix from the partial observation. In this paper, we explore the convenient Hankel structure and propose a novel non-convex algorithm, coined Hankel Structured Gradient Descent (HSGD), for large-scale robust Hankel matrix completion problems. HSGD is highly computing- and sample-efficient compared to the state-of-the-arts. The recovery guarantee with a linear convergence rate has been established for HSGD under some mild assumptions. The empirical advantages of HSGD are verified on both synthetic datasets and real-world nuclear magnetic resonance signals.

Low-rank matrix estimation under heavy-tailed noise is challenging, both computationally and statistically. Convex approaches have been proven statistically optimal but suffer from high computational costs, especially since robust loss functions are usually non-smooth. More recently, computationally fast non-convex approaches via sub-gradient descent are proposed, which, unfortunately, fail to deliver a statistically consistent estimator even under sub-Gaussian noise. In this paper, we introduce a novel Riemannian sub-gradient (RsGrad) algorithm which is not only computationally efficient with linear convergence but also is statistically optimal, be the noise Gaussian or heavy-tailed. Convergence theory is established for a general framework and specific applications to absolute loss, Huber loss, and quantile loss are investigated. Compared with existing non-convex methods, ours reveals a surprising phenomenon of dual-phase convergence. In phase one, RsGrad behaves as in a typical non-smooth optimization that requires gradually decaying stepsizes. However, phase one only delivers a statistically sub-optimal estimator which is already observed in the existing literature. Interestingly, during phase two, RsGrad converges linearly as if minimizing a smooth and strongly convex objective function and thus a constant stepsize suffices. Underlying the phase-two convergence is the smoothing effect of random noise to the non-smooth robust losses in an area close but not too close to the truth. Lastly, RsGrad is applicable for low-rank tensor estimation under heavy-tailed noise where a statistically optimal rate is attainable with the same phenomenon of dual-phase convergence, and a novel shrinkage-based second-order moment method is guaranteed to deliver a warm initialization. Numerical simulations confirm our theoretical discovery and showcase the superiority of RsGrad over prior methods., Comment: This manuscript is superseded by the new one (arXiv:2305.06199). There will be no further update of this manuscript and it will not be submitted for publications

A fundamental problem in phase retrieval is to reconstruct an unknown signal from a set of magnitude-only measurements. In this work we introduce three novel quotient intensity-based models (QIMs) based a deep modification of the traditional intensity-based models. A remarkable feature of the new loss functions is that the corresponding geometric landscape is benign under the optimal sampling complexity. When the measurements $ a_i\in \Rn$ are Gaussian random vectors and the number of measurements $m\ge Cn$, the QIMs admit no spurious local minimizers with high probability, i.e., the target solution $ x$ is the unique global minimizer (up to a global phase) and the loss function has a negative directional curvature around each saddle point. Such benign geometric landscape allows the gradient descent methods to find the global solution $x$ (up to a global phase) without spectral initialization., Comment: 41 pages

A fundamental task in phase retrieval is to recover an unknown signal $\vx\in \Rn$ from a set of magnitude-only measurements $y_i=\abs{\nj{\va_i,\vx}}, \; i=1,\ldots,m$. In this paper, we propose two novel perturbed amplitude models (PAMs) which have non-convex and quadratic-type loss function. When the measurements $ \va_i \in \Rn$ are Gaussian random vectors and the number of measurements $m\ge Cn$, we rigorously prove that the PAMs admit no spurious local minimizers with high probability, i.e., the target solution $ \vx$ is the unique global minimizer (up to a global phase) and the loss function has a negative directional curvature around each saddle point. Thanks to the well-tamed benign geometric landscape, one can employ the vanilla gradient descent method to locate the global minimizer $\vx$ (up to a global phase) without spectral initialization. We carry out extensive numerical experiments to show that the gradient descent algorithm with random initialization outperforms state-of-the-art algorithms with spectral initialization in empirical success rate and convergence speed., Comment: 60 pages

In this work we propose a nonconvex two-stage \underline{s}tochastic \underline{a}lternating \underline{m}inimizing (SAM) method for sparse phase retrieval. The proposed algorithm is guaranteed to have an exact recovery from $O(s\log n)$ samples if provided the initial guess is in a local neighbour of the ground truth. Thus, the proposed algorithm is two-stage, first we estimate a desired initial guess (e.g. via a spectral method), and then we introduce a randomized alternating minimization strategy for local refinement. Also, the hard-thresholding pursuit algorithm is employed to solve the sparse constraint least square subproblems. We give the theoretical justifications that SAM find the underlying signal exactly in a finite number of iterations (no more than $O(\log m)$ steps) with high probability. Further, numerical experiments illustrates that SAM requires less measurements than state-of-the-art algorithms for sparse phase retrieval problem.

We study the problem of estimating precision matrices in Gaussian distributions that are multivariate totally positive of order two ($\mathrm{MTP}_2$). The precision matrix in such a distribution is an M-matrix. This problem can be formulated as a sign-constrained log-determinant program. Current algorithms are designed using the block coordinate descent method or the proximal point algorithm, which becomes computationally challenging in high-dimensional cases due to the requirement to solve numerous nonnegative quadratic programs or large-scale linear systems. To address this issue, we propose a novel algorithm based on the two-metric projection method, incorporating a carefully designed search direction and variable partitioning scheme. Our algorithm substantially reduces computational complexity, and its theoretical convergence is established. Experimental results on synthetic and real-world datasets demonstrate that our proposed algorithm provides a significant improvement in computational efficiency compared to the state-of-the-art methods.