Leveraging Diversity and Sparsity in Blind Deconvolution by Ahmed, Ali, Demanet, Laurent

Get full text
Get full text
Get full text

Explicit Construction of RIP Matrices Is Ramsey‐Hard by Gamarnik, David

“…While it is known that random matrices satisfy the RIP with high probability even for n = logO(1)p, the explicit deteministic construction of such matrices defied the repeated efforts, and most of the known approaches hit the so-called (Formula presented.) sparsity bottleneck. The notable exception is the work by Bourgain et al. constructing an n × p RIP matrix with sparsity s = Θ(n1/2 + ϵ), but in the regime n = Ω(p1 − δ). …”
Get full text

Scaling law for recovering the sparsest element in a subspace by Demanet, Laurent, Hand, Paul

“…If sparsity is interpreted in an ℓ1/ℓ∞ sense, then the scaling law cannot be better than s≲n/√k. …”
Get full text
Get full text

Seeded graph matching via large neighborhood statistics by Mossel, E, Xu, J

“…We show that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of vertices n. …”
Get full text

Estimation of functionals of sparse covariance matrices by Fan, Jianqing, Rigollet, Philippe, Wang, Weichen

“…Specifically, we show that simple plug-in procedures based on thresholded estimators of correlation matrices are sparsity-adaptive and minimax optimal over a large class of correlation matrices. …”
Get full text
Get full text

Compressive wave computation by Demanet, Laurent, Peyre, Gabriel

“…While a linear superposition of eigenfunctions can fail to properly synthesize the solution if a single term is missing, it is shown that solving a sparsity-promoting ℓ 1 minimization problem can vastly enhance the quality of recovery. …”
Get full text
Get full text

Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods by Vanderbei, Robert, Lin, Kevin, Liu, Han, Wang, Lie

“…We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as ℓ[subscript 1]_ℓ[subscript s] and Mirror Prox regardless of the sparsity level or problem size.…”
Get full text
Get full text