The Average-Case Time Complexity of Certifying the Restricted Isometry Property.

Yunzi Ding Dmitriy Kunisky Alexander S. Wein Afonso S. Bandeira

Published in: CoRR (2020)

Keyphrases

average case
worst case
average case complexity
uniform distribution
worst case analysis
upper bound
learning curves
lower bound
np hard
machine learning
computational complexity
feature selection
semi supervised
vector field
decision problems
data compression
data sets