Optimal Detection of Sparse Signal Segments

on YouTube ↗39m

" summary

Derives precise detection thresholds and practical procedures for sparse segments in a length-n sequence, proving optimal rates and phase transitions. Uses a linear scan statistic (likelihood ratio) when the segment shape is known, achieving detection if amplitude^2 ≳ C·log n / d where d is segment length; uses a quadratic scan on centered squares when shape is unknown, with a short/long d regime and a √(log n) normalization; exploits smoothness by binning (bin size ≈ log n) with a critical smoothness α = 1/4 kink and implements a multiscale scan plus iterative removal to locate multiple segments.

AI-written summary · about

" chapters (19)

1. 0:00OPTIMAL DETECTION OF SPARSE SIG- NAL SEGMENTS
2. 1:08COPY NUMBER VARIATION
3. 2:36PEAK DETECTION
4. 3:38SPARSE SIGNAL DETECTION
5. 4:47EFFECT OF AMPLITUDE
6. 5:29EFFECT OF DURATION
7. 6:38SIGNALS WITH KNOWN SHAPE
8. 8:47SCAN FOR KNOWN SIGNAL
9. 13:58SIGNALS WITH ARBITRARY SHAPE
10. 15:00OPTIMALITY
11. 15:51LINEAR VS QUADRATIC SCAN
12. 18:25OPTIMAL RATES OF DETECTION
13. 20:21SCAN FOR SMOOTH SIGNALS
14. 21:45HOW MANY BINS?
15. 25:38OPTIMAL RATE OF DETECTION
16. 27:21EFFECT OF "BINNING"
17. 28:28ADAPTATION AND MULTISCALE SCAN
18. 29:56MULTIPLE SEGMENTS
19. 31:53SUMMARY

" related talks

• 26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement ProcessesSidharth Jaggi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 27mDetection and Estimation through an Information Theory LensSergio Verdú · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix EstimationCynthia Rush · Rigorous Evidence for Information-Computation Trade-offs
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 31mPlanted Geometric Matching ProblemsDmitriy (Tim) Kunisky · Rigorous Evidence for Information-Computation Trade-offs
• 21mLucky Talk: Chebyshev Polynomials, Moment Matching and Optimal Estimation of the UnseenYihong Wu · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 45mCommunity Detection with the Non-Backtracking OperatorMarc Lelarge · Random Instances and Phase Transitions (Simons Institute, 2016)