We show that solutions to the popular convex matrix LASSO problem (nuclear-norm--penalized linear least-squares) have low rank under similar assumptions as required by classical low-rank matrix sensing error bounds. Although the purpose of the nuclear norm penalty is to promote low solution rank, a proof has not yet (to our knowledge) been provided outside very specific circumstances. Furthermore, we show that this result has significant theoretical consequences for nonconvex rank-constrained optimization approaches. Specifically, we show that if (a) the ground truth matrix has low rank, (b) the (linear) measurement operator has the matrix restricted isometry property (RIP), and (c) the measurement error is small enough relative to the nuclear norm penalty, then the (unique) LASSO solution has rank (approximately) bounded by that of the ground truth. From this, we show (a) that a low-rank--projected proximal gradient descent algorithm will converge linearly to the LASSO solution from any initialization, and (b) that the nonconvex landscape of the low-rank Burer-Monteiro--factored problem formulation is benign in the sense that all second-order critical points are globally optimal and yield the LASSO solution.
相關內容
The Council of the European Union (EU) is one of the main decision-making bodies of the EU. Many decisions require a qualified majority: the support of 55% of the member states (currently 15) that represent at least 65% of the total population. We investigate how the power distribution, based on the Shapley-Shubik index, and the proportion of winning coalitions change if these criteria are modified within reasonable bounds. The power of the two countries with about 4% of the total population each is found to be almost flat. The level of decisiveness decreases if the population criterion is above 68\% or the states criterion is at least 17. The proportion of winning coalitions can be increased from 13.2% to 20.8% (30.1%) such that the maximal relative change in the Shapley-Shubik indices remains below 3.5% (5.5%). Our results are indispensable to evaluate any proposal for reforming the qualified majority voting system.
Many machine learning applications are naturally formulated as optimization problems on Riemannian manifolds. The main idea behind Riemannian optimization is to maintain the feasibility of the variables while moving along a descent direction on the manifold. This results in updating all the variables at every iteration. In this work, we provide a general framework for developing computationally efficient coordinate descent (CD) algorithms on matrix manifolds that allows updating only a few variables at every iteration while adhering to the manifold constraint. In particular, we propose CD algorithms for various manifolds such as Stiefel, Grassmann, (generalized) hyperbolic, symplectic, and symmetric positive (semi)definite. While the cost per iteration of the proposed CD algorithms is low, we further develop a more efficient variant via a first-order approximation of the objective function. We analyze their convergence and complexity, and empirically illustrate their efficacy in several applications.
We present a numerical scheme for the solution of the initial-value problem for the ``bad'' Boussinesq equation. The accuracy of the scheme is tested by comparison with exact soliton solutions as well as with recently obtained asymptotic formulas for the solution.
Gaussian elimination is the most popular technique for solving a dense linear system. Large errors in this procedure can occur in floating point arithmetic when the matrix's growth factor is large. We study this potential issue and how perturbations can improve the robustness of the Gaussian elimination algorithm. In their 1989 paper, Higham and Higham characterized the complete set of real n by n matrices that achieves the maximum growth factor under partial pivoting. This set of matrices serves as the critical focus of this work. Through theoretical insights and empirical results, we illustrate the high sensitivity of the growth factor of these matrices to perturbations and show how subtle changes can be strategically applied to matrix entries to significantly reduce the growth, thus enhancing computational stability and accuracy.
In this work, we analyze the convergence rate of randomized quasi-Monte Carlo (RQMC) methods under Owen's boundary growth condition [Owen, 2006] via spectral analysis. Specifically, we examine the RQMC estimator variance for the two commonly studied sequences: the lattice rule and the Sobol' sequence, applying the Fourier transform and Walsh--Fourier transform, respectively, for this analysis. Assuming certain regularity conditions, our findings reveal that the asymptotic convergence rate of the RQMC estimator's variance closely aligns with the exponent specified in Owen's boundary growth condition for both sequence types. We also provide analysis for certain discontinuous integrands.
A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give several new and efficient protocols: an estimator of state fidelity, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.
We present the ARR2 prior, a joint prior over the auto-regressive components in Bayesian time-series models and their induced $R^2$. Compared to other priors designed for times-series models, the ARR2 prior allows for flexible and intuitive shrinkage. We derive the prior for pure auto-regressive models, and extend it to auto-regressive models with exogenous inputs, and state-space models. Through both simulations and real-world modelling exercises, we demonstrate the efficacy of the ARR2 prior in improving sparse and reliable inference, while showing greater inference quality and predictive performance than other shrinkage priors. An open-source implementation of the prior is provided.
Multivariate Cryptography is one of the main candidates for Post-quantum Cryptography. Multivariate schemes are usually constructed by applying two secret affine invertible transformations $\mathcal S,\mathcal T$ to a set of multivariate polynomials $\mathcal{F}$ (often quadratic). The secret polynomials $\mathcal{F}$ posses a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials $\mathcal G=\mathcal S\circ\mathcal F\circ\mathcal T$ look like random polynomials. The polynomials $\mathcal G$ and $\mathcal F$ are said to be affine equivalent. In this article, we present a more general way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions.
We consider the nonparametric regression problem when the covariates are located on an unknown smooth compact submanifold of a Euclidean space. Under defining a random geometric graph structure over the covariates we analyze the asymptotic frequentist behaviour of the posterior distribution arising from Bayesian priors designed through random basis expansion in the graph Laplacian eigenbasis. Under Holder smoothness assumption on the regression function and the density of the covariates over the submanifold, we prove that the posterior contraction rates of such methods are minimax optimal (up to logarithmic factors) for any positive smoothness index.
We consider the application of the generalized Convolution Quadrature (gCQ) to approximate the solution of an important class of sectorial problems. The gCQ is a generalization of Lubich's Convolution Quadrature (CQ) that allows for variable steps. The available stability and convergence theory for the gCQ requires non realistic regularity assumptions on the data, which do not hold in many applications of interest, such as the approximation of subdiffusion equations. It is well known that for non smooth enough data the original CQ, with uniform steps, presents an order reduction close to the singularity. We generalize the analysis of the gCQ to data satisfying realistic regularity assumptions and provide sufficient conditions for stability and convergence on arbitrary sequences of time points. We consider the particular case of graded meshes and show how to choose them optimally, according to the behaviour of the data. An important advantage of the gCQ method is that it allows for a fast and memory reduced implementation. We describe how the fast and oblivious gCQ can be implemented and illustrate our theoretical results with several numerical experiments.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191