Reconstruction of signals from undersampled and noisy measurements is a topic of considerable interest. Sharpness conditions directly control the recovery performance of restart schemes for first-order methods without the need for restrictive assumptions such as strong convexity. However, they are challenging to apply in the presence of noise or approximate model classes (e.g., approximate sparsity). We provide a first-order method: Weighted, Accelerated and Restarted Primal-dual (WARPd), based on primal-dual iterations and a novel restart-reweight scheme. Under a generic approximate sharpness condition, WARPd achieves stable linear convergence to the desired vector. Many problems of interest fit into this framework. For example, we analyze sparse recovery in compressed sensing, low-rank matrix recovery, matrix completion, TV regularization, minimization of $\|Bx\|_{l^1}$ under constraints ($l^1$-analysis problems for general $B$), and mixed regularization problems. We show how several quantities controlling recovery performance also provide explicit approximate sharpness constants. Numerical experiments show that WARPd compares favorably with specialized state-of-the-art methods and is ideally suited for solving large-scale problems. We also present a noise-blind variant based on the Square-Root LASSO decoder. Finally, we show how to unroll WARPd as neural networks. This approximation theory result provides lower bounds for stable and accurate neural networks for inverse problems and sheds light on architecture choices. Code and a gallery of examples are made available online as a MATLAB package.
相關內容
We deal with a long-standing problem about how to design an energy-stable numerical scheme for solving the motion of a closed curve under {\sl anisotropic surface diffusion} with a general anisotropic surface energy $\gamma(\boldsymbol{n})$ in two dimensions, where $\boldsymbol{n}$ is the outward unit normal vector. By introducing a novel symmetric positive definite surface energy matrix $Z_k(\boldsymbol{n})$ depending on the Cahn-Hoffman $\boldsymbol{\xi}$-vector and a stabilizing function $k(\boldsymbol{n})$, we first reformulate the anisotropic surface diffusion into a conservative form and then derive a new symmetrized variational formulation for the anisotropic surface diffusion with weakly or strongly anisotropic surface energies. A semi-discretization in space for the symmetrized variational formulation is proposed and its area (or mass) conservation and energy dissipation are proved. The semi-discretization is then discretized in time by either an implicit structural-preserving scheme (SP-PFEM) which preserves the area in the discretized level or a semi-implicit energy-stable method (ES-PFEM) which needs only solve a linear system at each time step. Under a relatively simple and mild condition on $\gamma(\boldsymbol{n})$, we show that both SP-PFEM and ES-PFEM are unconditionally energy-stable for almost all anisotropic surface energies $\gamma(\boldsymbol{n})$ arising in practical applications. Specifically, for several commonly-used anisotropic surface energies, we construct $Z_k(\boldsymbol{n})$ explicitly. Finally, extensive numerical results are reported to demonstrate the high performance of the proposed numerical schemes.
Many recent problems in signal processing and machine learning such as compressed sensing, image restoration, matrix/tensor recovery, and non-negative matrix factorization can be cast as constrained optimization. Projected gradient descent is a simple yet efficient method for solving such constrained optimization problems. Local convergence analysis furthers our understanding of its asymptotic behavior near the solution, offering sharper bounds on the convergence rate compared to global convergence analysis. However, local guarantees often appear scattered in problem-specific areas of machine learning and signal processing. This manuscript presents a unified framework for the local convergence analysis of projected gradient descent in the context of constrained least squares. The proposed analysis offers insights into pivotal local convergence properties such as the condition of linear convergence, the region of convergence, the exact asymptotic rate of convergence, and the bound on the number of iterations needed to reach a certain level of accuracy. To demonstrate the applicability of the proposed approach, we present a recipe for the convergence analysis of PGD and demonstrate it via a beginning-to-end application of the recipe on four fundamental problems, namely, linearly constrained least squares, sparse recovery, least squares with the unit norm constraint, and matrix completion.
In this work we consider algorithms for reconstructing time-varying data into a finite sum of discrete trajectories, alternatively, an off-the-grid sparse-spikes decomposition which is continuous in time. Recent work showed that this decomposition was possible by minimising a convex variational model which combined a quadratic data fidelity with dynamical Optimal Transport. We generalise this framework and propose new numerical methods which leverage efficient classical algorithms for computing shortest paths on directed acyclic graphs. Our theoretical analysis confirms that these methods converge to globally optimal reconstructions which represent a finite number of discrete trajectories. Numerically, we show new examples for unbalanced Optimal Transport penalties, and for balanced examples we are 100 times faster in comparison to the previously known method.
This paper introduces SPDE bridges with observation noise and contains an analysis of their spatially semidiscrete approximations. The SPDEs are considered in the form of mild solutions in an abstract Hilbert space framework suitable for parabolic equations. They are assumed to be linear with additive noise in the form of a cylindrical Wiener process. The observational noise is also cylindrical and SPDE bridges are formulated via conditional distributions of Gaussian random variables in Hilbert spaces. A general framework for the spatial discretization of these bridge processes is introduced. Explicit convergence rates are derived for a spectral and a finite element based method. It is shown that for sufficiently rough observation noise, the rates are essentially the same as those of the corresponding discretization of the original SPDE.
Fourth-order differential equations play an important role in many applications in science and engineering. In this paper, we present a three-field mixed finite-element formulation for fourth-order problems, with a focus on the effective treatment of the different boundary conditions that arise naturally in a variational formulation. Our formulation is based on introducing the gradient of the solution as an explicit variable, constrained using a Lagrange multiplier. The essential boundary conditions are enforced weakly, using Nitsche's method where required. As a result, the problem is rewritten as a saddle-point system, requiring analysis of the resulting finite-element discretization and the construction of optimal linear solvers. Here, we discuss the analysis of the well-posedness and accuracy of the finite-element formulation. Moreover, we develop monolithic multigrid solvers for the resulting linear systems. Two and three-dimensional numerical results are presented to demonstrate the accuracy of the discretization and efficiency of the multigrid solvers proposed.
In this paper, we investigate the problem of system identification for autonomous switched linear systems with complete state observations. We propose switched least squares method for the identification for switched linear systems, show that this method is strongly consistent, and derive data-dependent and data-independent rates of convergence. In particular, our data-dependent rate of convergence shows that, almost surely, the system identification error is $\mathcal{O}\big(\sqrt{\log(T)/T} \big)$ where $T$ is the time horizon. These results show that our method for switched linear systems has the same rate of convergence as least squares method for non-switched linear systems. We compare our results with those in the literature. We present numerical examples to illustrate the performance of the proposed system identification method.
Invariance-based randomization tests -- such as permutation tests, rotation tests, or sign changes -- are an important and widely used class of statistical methods. They allow drawing inferences under weak assumptions on the data distribution. Most work focuses on their type I error control properties, while their consistency properties are much less understood. We develop a general framework and a set of results on the consistency of invariance-based randomization tests in signal-plus-noise models. Our framework is grounded in the deep mathematical area of representation theory. We allow the transforms to be general compact topological groups, such as rotation groups, acting by general linear group representations. We study test statistics with a generalized sub-additivity property. We apply our framework to a number of fundamental and highly important problems in statistics, including sparse vector detection, testing for low-rank matrices in noise, sparse detection in linear regression, and two-sample testing. Comparing with minimax lower bounds, we find perhaps surprisingly that in some cases, randomization tests detect signals at the minimax optimal rate.
We apply the method of penalization to the Dirichlet problem for the Navier-Stokes-Fourier system governing the motion of a general viscous compressible fluid confined to a bounded Lipschitz domain. The physical domain is embedded into a large cube on which the periodic boundary conditions are imposed. The original boundary conditions are enforced through a singular friction term in the momentum equation and a heat source/sink term in the internal energy balance. The solutions of the penalized problem are shown to converge to the solution of the limit problem. Numerical experiments are performed to illustrate the efficiency of the method.
Erd\H{o}s and Purdy, and later Agarwal and Sharir, conjectured that any set of $n$ points in $\mathbb R^{d}$ determine at most $Cn^{d/2}$ congruent $k$-simplices for even $d$. We obtain the first significant progress towards this conjecture, showing that this number is at most $C n^{3d/4}$ for $k<d$. As a consequence, we obtain an upper bound of $C n^{3d/4+2}$ for the number of similar $k$-simplices determined by $n$ points in $\mathbb R^d$, which improves the results of Agarwal, Apfelbaum, Purdy and Sharir. This problem is motivated by the problem of exact pattern matching. We also address Zarankiewicz-type questions of finding the maximum number of edges in semi-algebraic graphs with no $K_{u,u}$. Here, we improve the previous result of Fox, Pach, Sheffer, Suk, and Zahl, and Do for $d\le 4$, as well as for any $d$ and moderately large $u$. We get an improvement of their results for any $d$ and $u$ for unit-distance graphs, which was one of the main applications of their results. From a more general prospective, our results are proved using classical cutting techniques. In the recent years, we saw a great development of the polynomial partitioning method in incidence geometry that followed the breakthrough result by Guth and Katz. One consequence of that development is that the attention of the researchers in incidence geometry swayed in polynomial techniques. In this paper, we argue that there is a number of open problems where classical techniques work better.
$k$-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.93, even in the plane, if one insists the dependence on $k$ in the running time be polynomial. Without this restriction, a classic algorithm yields a $2^{O((k\log k)/{\epsilon})}dn$-time $(1+\epsilon)$-approximation for Euclidean $k$-center, where $d$ is the dimension. We give a faster algorithm for small dimensions: roughly speaking an $O^*(2^{O((1/\epsilon)^{O(d)} \cdot k^{1-1/d} \cdot \log k)})$-time $(1+\epsilon)$-approximation. In particular, the running time is roughly $O^*(2^{O((1/\epsilon)^{O(1)}\sqrt{k}\log k)})$ in the plane. We complement our algorithmic result with a matching hardness lower bound. We also consider a well-studied generalization of $k$-center, called Non-uniform $k$-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a $2^{O(k\log k)}n^2$ time $3$-approximation for NUkC in general metrics, and a $2^{O((k\log k)/\epsilon)}dn$ time $(1+\epsilon)$-approximation for Euclidean NUkC. The latter time bound matches the bound for $k$-center.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191