Paper studies superconvergence on surface meshes using gradient recovery.
problem Proving superconvergence on deviated surfaces.
method Introduces geometric supercloseness and an algorithmic framework for gradient recovery.
result Validates theoretical results with numerical examples.
This paper tackles tensor recovery from noisy and multi-level quantized measurements.
problem Tensors from multi-level quantized measurements.
method Nonconvex optimization problem with alternating proximal gradient descent.
result The recovery error diminishes to zero with increasing tensor dimensions.
This paper investigates gradient recovery schemes for data defined on discretized manifolds. The proposed method, parametric polynomial preserving recovery (PPPR), does not require the tangent spaces of the exact manifolds, and they have been assumed for some significant gradient recovery methods in the literature. Ano…
We propose a generic framework based on a new stochastic variance-reduced gradient descent algorithm for accelerating nonconvex low-rank matrix recovery. Starting from an appropriate initial estimator, our proposed algorithm performs projected gradient descent based on a novel semi-stochastic gradient specifically desi…
Gradient descent recovers low-rank matrices from corrupted measurements with double over-parameterization.
problem Robust recovery of low-rank matrices from grossly corrupted measurements.
method Gradient descent with discrepant learning rates for double over-parameterized models.
result Gradient descent with discrepant learning rates provably recovers the underlying matrix without prior knowledge on rank or sparsity.
Improved stability for matrix recovery from rank-one measurements.
problem Phase retrieval problem of recovering rank-one positive semidefinite matrices.
method Developed a smoothing Newton method based on Bures-Wasserstein gradient descent.
result Superlinear convergence with rigorous guarantees and stable implementation.
Paper develops methods for non-quadratic loss low-rank matrix recovery.
problem Recovery of low-rank matrices with non-quadratic losses.
method Projected gradient method with a regularity projection oracle.
result Projected gradient method converges globally and linearly.
Study recovers spike order in noisy tensor estimation without SNR assumptions.
problem Estimating multiple signal vectors from noisy tensor observations.
method Gradient flow optimization of a nonconvex function.
result Determines sample complexity for efficient permutation recovery.
Nonnegative low-rank matrix recovery can have spurious local minima.
problem Nonnegative low-rank matrix recovery problems can have spurious local minima.
method Investigated projected gradient methods for nonnegative low-rank recovery problems.
result Benign nonconvexity holds in the fully-observed case with RIP constant δ=0 but fails in the partially-observed case and higher-rank ground truths.
Study iterative regularization for linear models with convex bias, improving robust sparse recovery.
problem Improving robust sparse recovery with iterative regularization for linear models.
method Primal-dual gradient approach, analyzing convergence in presence of noise, combining regularization and optimization.
result Theoretical results show state-of-the-art performances with computational speed-ups.
New method avoids spurious critical points for low-rank matrix recovery.
problem Low-rank matrix recovery problems on Riemannian manifold.
method Riemannian gradient descent with random initialization.
result Riemannian gradient descent avoids spurious critical points and converges nearly linearly.
Scaled gradient descent improves matrix recovery for ill-conditioned matrices with optimal sampling complexity.
problem Recovering low-rank matrices from limited measurements efficiently and accurately.
method Scaled gradient descent (ScaledGD) with optimal sample complexity and improved iteration complexity.
result ScaledGD achieves optimal sample complexity and improved iteration complexity for ill-conditioned matrices.
Study shows overparameterization helps shallow neural networks recover signals in high dimensions.
problem Signal recovery in shallow neural networks with overparameterization.
method Gradient flow on population risk, Gaussian distribution assumption, high-dimensional limit analysis.
result Minimal overparameterization is sufficient for strong recovery of signals.
GNMR controls runtime stability in low-precision language model training.
problem Efficient low-precision training faces numerical risks at specific operators.
method GNMR compares gradient norms to historical means, applying bounded recovery actions.
result GNMR preserves high-fidelity quality with sparse, budgeted recovery.
RTC-GTNLN model recovers traffic data from missing values and noise.
problem Simultaneous missing data and noise in traffic data.
method Gradient tensor nuclear L1-L2 norm for robust tensor completion.
result RTC-GTNLN model outperforms existing methods in complex recovery scenarios.
We present a mathematical analysis of a non-convex energy landscape for robust subspace recovery. We prove that an underlying subspace is the only stationary point and local minimizer in a specified neighborhood under a deterministic condition on a dataset. If the deterministic condition is satisfied, we further show t…
Proposes using equivariant generative models for compressed sensing with unknown orientations.
problem Recovering signals with unknown orientations from underdetermined systems of linear measurements.
method Equivariant variational autoencoder as a generative prior for compressed sensing.
result Signals with unknown orientations can be recovered using iterative gradient descent on the latent space of equivariant models.
Paper uses SGLD to recover signals from generative models, proving convergence under mild conditions.
problem Signal recovery from generative priors in compressed sensing.
method Stochastic Gradient Langevin Dynamics (SGLD) for signal recovery.
result SGLD converges to the true signal under mild assumptions on the generative model.
New algorithm recovers matrices with unknown correspondences.
problem Recovering matrices from observations with unknown correspondences.
method Solves a nuclear norm minimization problem via proximal gradient with a Max-Oracle.
result Achieves state-of-the-art performance and high accuracy in recovering ground-truth correspondences.
We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial ti…
Untrained neural networks can recover natural images from few measurements.
problem Recovering natural images from a small number of measurements.
method Gradient descent on un-trained convolutional neural networks.
result Untrained neural networks can approximate reconstruct signals/images from a near minimal number of random measurements.
A new model for dynamic covariance recovery in neuroimaging data.
problem Estimating time-varying covariances in high-dimensional neuroimaging data.
method Nonconvex factorization into sparse spatial and smooth temporal components, combined with spectral initialization and gradient descent.
result The proposed method achieves linear convergence and superior performance compared to existing approaches.
Binary Iterative Hard Thresholding converges with optimal number of 1-bit measurements.
problem Recovering sparse signals from 1-bit compressed measurements.
method Binary Iterative Hard Thresholding (BIHT) algorithm.
result BIHT converges with only O(k/ε) measurements, optimal for recovery.
SGD recovers multiple signal vectors in noisy tensor PCA.
problem Estimating multiple signal vectors from noisy tensor observations.
method Online stochastic gradient descent (SGD) in high dimensions with detailed analysis of correlations.
result Sequential elimination of correlations allows recovery of all spikes from Np−2 samples. We propose two approaches of locally adaptive activation functions namely, layer-wise and neuron-wise locally adaptive activation functions, which improve the performance of deep and physics-informed neural networks. The local adaptation of activation function is achieved by introducing a scalable parameter in each lay…
Gradient descent with early stopping achieves optimal sparse recovery.
problem Sparse regression with gradient descent and early stopping.
method Gradient descent on depth-N networks with early stopping.
result Implicit sparse regularization occurs with early stopping for general depth N.
Robust tensor recovery plays an instrumental role in robustifying tensor decompositions for multilinear data analysis against outliers, gross corruptions and missing values and has a diverse array of applications. In this paper, we study the problem of robust low-rank tensor recovery in a convex optimization framework,…
We consider estimating a piecewise-constant image, or a gradient-sparse signal on a general graph, from noisy linear measurements. We propose and study an iterative algorithm to minimize a penalized least-squares objective, with a penalty given by the "l_0-norm" of the signal's discrete graph gradient. The method proce…
When the linear measurements of an instance of low-rank matrix recovery satisfy a restricted isometry property (RIP)---i.e. they are approximately norm-preserving---the problem is known to contain no spurious local minima, so exact recovery is guaranteed. In this paper, we show that moderate RIP is not enough to elimin…
Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear sub-manifold of a high dimensional ambient space. We introduce SPIN, a first order projected gradient method to recover the signal components. Despite the…
New tensor recovery method improves efficiency under strict complementarity.
problem Efficiently recovering low-rank tensors using tensor nuclear norm.
method Developed strict complementarity condition for tensor nuclear norm ball and applied to gradient methods.
result Standard gradient methods achieve linear convergence and nearly linear runtime under strict complementarity.
The paper validates a method for recovering over-parameterized matrices and images from noisy measurements.
problem Recovering a low-rank matrix from noisy measurements when the rank is unknown.
method Using gradient descent with small random initialization on a nonconvex objective function built from a rank-overspecified factored representation of the matrix variable.
result Gradient descent iterations converge to the ground-truth matrix under certain conditions and can be stopped efficiently to detect a nearly optimal estimator.
As surrogate functions of L0-norm, many nonconvex penalty functions have been proposed to enhance the sparse vector recovery. It is easy to extend these nonconvex penalty functions on singular values of a matrix to enhance low-rank matrix recovery. However, different from convex optimization, solving the nonconvex l…
The paper analyzes conditions for solving low-rank matrix recovery problems with noisy measurements.
problem Low-rank matrix recovery with corrupted measurements.
method Analysis of the restricted isometry property (RIP) and local search methods.
result Sharp bounds on the maximum distance between local minimizers and the ground truth.
Sub-gradient method recovers low-rank matrices robustly from noisy measurements.
problem Recovering low-rank matrices from noisy measurements with unknown rank.
method Sub-gradient method with small initialization, robust to over-parameterization and noise.
result Sub-gradient method converges exponentially fast to the true solution under noisy and over-parameterized conditions.
Study inverse problems with measure samples, improving estimator calibration and recovery.
problem Inverse problems with unknown potentials observed through measure samples.
method Introduced convex empirical objectives and sharpened Fenchel--Young losses for finite-dimensional potential classes.
result High-probability parameter recovery bounds for inverse entropic unbalanced optimal transport and inverse JKO learning.
We study the problem of estimating low-rank matrices from linear measurements (a.k.a., matrix sensing) through nonconvex optimization. We propose an efficient stochastic variance reduced gradient descent algorithm to solve a nonconvex optimization problem of matrix sensing. Our algorithm is applicable to both noisy and…
Paper proposes LC-Checkpoint for efficient deep learning model checkpoints.
problem Efficient construction of checkpoints for deep learning models.
method Lossy compression scheme using quantization and priority promotion with Huffman coding.
result LC-Checkpoint achieves up to 28x compression and 5.77x speedup over SCAR.
Paper develops a new algorithm for sparse signal recovery.
problem Sparse signal recovery from noisy observations.
method Iterative Stochastic Optimization using Stochastic Mirror Descent.
result Linear convergence during preliminary phase of the routine.
New tensor recovery method uses Riemannian optimization on Segre manifold.
problem Recovering low-rank tensors from noisy measurements.
method Riemannian Gradient Descent (RGD) and Riemannian Gauss-Newton (RGN) algorithms over the Segre manifold.
result Proven convergence rates for RGD and RGN under mild noise assumptions.
Efficiently recovers low-tubal-rank tensors from few measurements.
problem Recovering tensors with low tubal-rank from limited measurements.
method Factorization and factorized gradient descent.
result Factorized gradient descent reduces computational costs and storage requirements.
This work improves dictionary learning speed without sacrificing accuracy.
problem Prohibitive computational cost of standard dictionary learning methods.
method Approximate dictionary learning using unrolling and gradient descent.
result Unrolling outperforms standard methods in support estimation and early iterations.
Accelerated gradient method tackles nonconvex penalties in sparse learning.
problem Optimizing nonconvex penalties in sparse statistical learning.
method Generalized Nesterov's accelerated gradient method with hyperparameter optimization.
result Convergence can be made considerably faster with optimal hyperparameters.
Quantization-aware training can recover accuracy lost by post-training quantization.
problem Post-training quantization (PTQ) can fail sharply at aggressive bitwidths.
method A unified geometric framework that explains PTQ failure and QAT recovery.
result QAT has a useful bias that steers iterates back into the basin.
Paper tackles phase retrieval with robust gradient descent for noisy data.
problem Recover signals from magnitude measurements with noise and corruption.
method Robust gradient descent applied to Wirtinger Flow algorithm.
result Improves algorithm's robustness to heavy-tailed noise and adversarial corruption.
Paper introduces ENZ to measure significant coefficients in sparse recovery, improving over classical methods.
problem Numerical noise creates long tails of negligible coefficients in sparse recovery.
method Entropy-based notion of effective sparsity (ENZ) to measure significant coefficients, proving stability under restricted isometry condition.
result ENZ decomposes into support cardinality and efficiency factor, providing a precise measure of sparsity.
Gradient EM converges globally for over-parameterized Gaussian mixtures.
problem Recovering ground truth Gaussian mixtures with over-parameterized models.
method Gradient EM with over-parameterization, using Hermite polynomials and tensor decomposition.
result Gradient EM globally converges to ground truth with n=Ω(mlogm) over-parameterization. The paper shows how label noise in training can lead to solutions that solve a Lasso program.
problem Understanding the implicit bias of training algorithms in overparametrised models.
method Analyzing the continuous time version of the training dynamics of a quadratically parametrised model.
result The stochastic flow implicitly solves a Lasso program, providing convergence guarantees and support recovery conditions.