-
Compressed Sensing
Introduction Compressed Sensing(CS)이란 어떠한 신호(signal)를 효율적으로 수집 및 복원하는 기법으로, 이미지 압축이나 복원, 카메라 센서 등에 사용되는 기술이다. 간단히 예를 들어 설명하자면, N개의 픽셀로 이루어진 사진을 얻기 위해서는 N번의 observation이 필요하다고 생각하는 것이 일반적이라면 CS를 이용하는 경우 훨씬 적은 측정으로도 이를 loss 없이, 또는 매우 적은 loss로 얻을 수 있다. 이 글에서는 CS 이론의 배경과 기반 및 실제 적용에 대해 간략히 살펴본다. History Nyquist-Shannon sampling theorem $f(t)$ 가 $B$ 헤르츠 이상의 주파수를 가지지 않을 때,...
-
Relevant points in Nearest-Neighbor Classification
Introduction $k$-nearest neighbor classification이란, $d$차원 공간 위의 point cloud들 (training set)과 그 class가 주어져 있을 때, 새로운 점의 class를 예측하는 한 가지 방법입니다. 자신과 가장 가까운 $k$개의 점의 label 중 가장 많은 것을 선택하는 방법으로, 고전적인 pattern recognition method 중 하나로 소개되었습니다. 오늘은 이 중 그나마 알고리즘의 시각에서 조명이 가능한 $k = 1$ case, 즉, nearest-neighbor classification에 대해 알아봅시다. 1-NN classification and Voronoi diagram $d = 2$인 경우, 어떤 점 $p$의 nearest neighbor가 $q$일 필요충분조건은...
-
Tweakable block ciphers
1. Introduction 안녕하세요, 이번 글에서는 Moses Liskov, Ronald L. Rivest and David Wagner가 작성한 Tweakable Block Ciphers(링크) 논문을 주제로 정했습니다. 참고로 저자중 2번째에 위치한 Ronald L. Rivest는 RSA의 R입니다. 이 논문에서 최초로 Tweakable Block Ciphers라는 개념을 제안했고 이후 Tweak이라는 개념은 대칭키 분야에서 중요하게 쓰이고 있고 최근까지도 관련된 논문이 계속 제시되고 있습니다. 진정한 대가들은 학문에서 새로운 방향성을 제시한다고 하는데 이 논문이 딱 그런 상황에 걸맞는 논문이 맞지 않나 하는 생각이 듭니다. 이번 글을 통해 Tweakable block...
-
Sum over Subsets (SOS) DP
이번 글에서는 다이나믹 프로그래밍으로 Sum over Subsets (SOS) 문제를 푸는 방법을 대해 소개하겠습니다. SOS DP는 Codeforces에서 중상급 난이도의 문제로 종종 출제되는 흥미로운 테크닉이지만, 지금껏 한국어 자료를 찾아보기 어려웠기 때문에 SOS DP를 소개하는 Codeforces 블로그 글의 구성을 참고해서 한국어 소개글을 작성해 보았습니다. 또한 기존 글에서 한발 나아가서 어떤 직관을 통해 SOS DP를 이해할 수 있는지도 소개하려고 합니다. 이 글에서는 다음과 같은 표기를 사용할 것입니다. 비트마스크를 집합처럼 취급합니다. 예를 들어, $1101_{(2)} = 2^0 + 2^2 + 2^3$은...
-
Push Relabel Algorithm (2)
2월의 Push-Relabel algorithm 관련 글에 이어서 Push-relabel에 기반한 다항 시간 MCMF 알고리즘 (Cost Scaling)에 대해서 다룰 예정이다. 이 글에서는 일반적으로 알려진 Successive Shortest Path Algorithm보다 훨씬 더 효율적인 알고리즘을 다룬다. MCMF (Minimum-Cost Maximum-Flow) 문제는 알고리즘 대회 입문서에 다 소개되어 있는 중요한 문제이다. 2월 중순에 글이 올라온 뒤, 3월 1일 Almost-Linear Time Minimum Cost Flow 가 가능하다는 사실이 알려져서 많은 화제를 모았다. 당연하지만 이론전산에서 아주 중요한 연구 결과이고, 저자들은 아마 권위있는 상 하나 정도는 수상하지 않을까...