Living on the edge: phase transitions in convex programs with random data
From MaRDI portal
Publication:5177869
DOI10.1093/imaiai/iau005zbMath1339.90251arXiv1303.6672OpenAlexW2025223969MaRDI QIDQ5177869
Dennis Amelunxen, Michael B. McCoy, Martin Lotz, Joel A. Tropp
Publication date: 6 March 2015
Published in: Information and Inference (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.6672
convex optimizationphase transitionsintegral geometrycompressed sensingconic geometrynuclear norm minimization\(\ell_{1}\) minimizationrank-sparsity decompositionmorphological component analysis
Related Items
A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets, Randomized numerical linear algebra: Foundations and algorithms, Unnamed Item, Projections and angle sums of belt polytopes and permutohedra, Sharp global convergence guarantees for iterative nonconvex optimization with random data, Random cones in high dimensions II: Weyl cones, A theory of capacity and sparse neural encoding, A unified approach to uniform signal recovery from nonlinear observations, Analytic approach to variance optimization under an \(\mathcal{l}_1\) constraint, Grassmann angles and absorption probabilities of Gaussian convex hulls, EXPECTEDf‐VECTOR OF THE POISSON ZERO POLYTOPE AND RANDOM CONVEX HULLS IN THE HALF‐SPHERE, Unnamed Item, Sampling rates for \(\ell^1\)-synthesis, An identity for the coefficients of characteristic polynomials of hyperplane arrangements, Geometric and functional inequalities for log-concave probability sequences, Global optimization using random embeddings, Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions, The Lasso with general Gaussian designs with applications to hypothesis testing, On a Conjecture of Feige for Discrete Log-Concave Distributions, Angle sums of random polytopes, Persistent homology for low-complexity models, Consistent parameter estimation for Lasso and approximate message passing, On the volume of tubular neighborhoods of real algebraic varieties, Sparse recovery from extreme eigenvalues deviation inequalities, On the Convergence Rate of Projected Gradient Descent for a Back-Projection Based Objective, Signal Decomposition Using Masked Proximal Operators, Fundamental barriers to high-dimensional regression with convex penalties, High-dimensional asymptotics of likelihood ratio tests in the Gaussian sequence model under convex constraints, Positive hulls of random walks and bridges, Average-case complexity without the black swans, Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery, Stochastic Tverberg Theorems With Applications in Multiclass Logistic Regression, Separability, and Centerpoints of Data, Convex cones spanned by regular polytopes, A geometrical stability condition for compressed sensing, Conic support measures, The spherical convex floating body, Splitting tessellations in spherical spaces, A note on computing the smallest conic singular value, Geometric inference for general high-dimensional linear inverse problems, Random conical tessellations, Book Review: A mathematical introduction to compressive sensing, On the universality of noiseless linear estimation with respect to the measurement matrix, Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing, Sharp MSE bounds for proximal denoising, The restricted isometry property of block diagonal matrices for group-sparse signal recovery, Low rank matrix recovery from rank one measurements, High-dimensional change-point estimation: combining filtering with convex optimization, Concentration inequalities for ultra log-concave distributions, Adaptation in multivariate log-concave density estimation, Convex hulls of random walks, hyperplane arrangements, and Weyl chambers, Compressed sensing for finite-valued signals, \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?, Compressed sensing of data with a known distribution, Conic intrinsic volumes of Weyl chambers, Generalizing CoSaMP to signals from a union of low dimensional linear subspaces, Intrinsic volumes of polyhedral cones: a combinatorial perspective, The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression, Contextual Search via Intrinsic Volumes, Estimating piecewise monotone signals, Angle sums of Schläfli orthoschemes, Generic error bounds for the generalized Lasso with sub-exponential data, Fast and Reliable Parameter Estimation from Nonlinear Observations, Sparse disjointed recovery from noninflating measurements, On the risk of convex-constrained least squares estimators under misspecification, Sharp recovery bounds for convex demixing, with applications, Robust analysis ℓ1-recovery from Gaussian measurements and total variation minimization, On estimation of isotonic piecewise constant signals, Terracini convexity, Analysis \(\ell_1\)-recovery with frames and Gaussian measurements, A Rice method proof of the null-space property over the Grassmannian, CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Guarantees of total variation minimization for signal recovery, High-dimensional estimation with geometric constraints: Table 1., Concentration of the Intrinsic Volumes of a Convex Body, Stable low-rank matrix recovery via null space properties, Flavors of Compressive Sensing, The existence of maximum likelihood estimate in high-dimensional binary response generalized linear models, Concentration of the Frobenius Norm of Generalized Matrix Inverses, Adaptive confidence sets in shape restricted regression, Adaptive risk bounds in unimodal regression, A multidimensional analogue of the arcsine law for the number of positive terms in a random walk, Optimal rates of statistical seriation, Structure from Randomness in Halfspace Learning with the Zero-One Loss, Nonparametric shape-restricted regression, An Introduction to Compressed Sensing, A new perspective on least squares under convex constraint, Recursive scheme for angles of random simplices, and applications to random polytopes, The geometry of hypothesis testing over convex cones: generalized likelihood ratio tests and minimax radii, Analytic solution to variance optimization with no short positions, Inexact primal–dual gradient projection methods for nonlinear optimization on convex set, Convex Coupled Matrix and Tensor Completion, Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all, Overcoming the limitations of phase transition by higher order analysis of regularization techniques, Sharp oracle inequalities for least squares estimators in shape restricted regression, Tightness of the maximum likelihood semidefinite relaxation for angular synchronization, On the subdifferential of symmetric convex functions of the spectrum for symmetric and orthogonally decomposable tensors, Beta polytopes and Poisson polyhedra: \(f\)-vectors and angles, The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square, Intersection probabilities and kinematic formulas for polyhedral cones, Estimation in High Dimensions: A Geometric Perspective, Convex Recovery of a Structured Signal from Independent Random Linear Measurements, Low Complexity Regularization of Linear Inverse Problems, On risk bounds in isotonic and other shape restricted regression problems, A Data-Independent Distance to Infeasibility for Linear Conic Systems, Faces in random great hypersphere tessellations, Unnamed Item, From Steiner formulas for cones to concentration of intrinsic volumes, Conical tessellations associated with Weyl chambers, Safe feature elimination for non-negativity constrained convex optimization, The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning, Guarantees of Riemannian Optimization for Low Rank Matrix Recovery, Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction, Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems, Distribution-free properties of isotonic regression, Isotonic regression in general dimensions, Convex geometry and its applications. Abstracts from the workshop held December 9--15, 2018, Unnamed Item, On a game of chance in Marc Elsberg's thriller ``GREED, Cones generated by random points on half-spheres and convex hulls of Poisson point processes, Precise statistical analysis of classification accuracies for adversarial training, Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks, Proof methods for robust low-rank matrix recovery, Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing, A new approach to weak convergence of random cones and polytopes, Fast Convex Pruning of Deep Neural Networks, Threshold phenomena for random cones
