📂행렬대수

스파스 행렬

정의

자연어에서 스파스^sparse란 희박하다, 희소하다는 의미로써 값이 $0$ 이면 값이 존재하지 않는 것이나 마찬가지로 간주하는 것에서 온 단어다. 스파서티^sparsity란 얼마나 많은 $0$ 으로 이루어졌는지에 대한 정도를 말한다.

스파스 행렬

그 성분이 대부분 $0$ 인 행렬을 스파스 행렬^{sparse matrix}이라 한다.

$S$-스파스 ¹

$\mathbf{v} \in \mathbb{R}^{d}$ 가 많아도 $S \ll d$ 개의 $0$ 이 아닌 성분을 가지고 있을 때 $\mathbf{x}$ 는 $S$-스파스^$S$-sparse하다고 한다. 이 때 정수 $S \in \mathbb{Z}$ 는 벡터 $\mathbf{v}$ 의 서포트 $\operatorname{supp} \mathbf{v} = \left\{ k : \mathbf{v}_{k} \ne 0 \right\}$ 에 대해 다음의 부등식을 만족한다. $$ \operatorname{card} \left( \operatorname{supp} \mathbf{v} \right) \le S $$ 여기서 $\operatorname{card}$ 는 카디널러티를 의미한다.

설명

순화로는 희박행렬 및 희소행렬이 있는데, 당연하지만 보통은 둘 다 안 쓰고 영어 발음 그대로 [스파스 매트릭스]라 읽는다. 스파스행렬은 단어 그대로 행렬에 ‘의미 있는’ 정보가 스파스한 행렬로 정의되는데, ‘대부분’이라는 단어가 쓰인 것에서 짐작할 수 있듯 수학적으로 엄밀한 정의는 아니다. 구체적인 $S$ 가 주어져서 ‘충분히 스파스’하다는 표현이 나올 땐 그 정의를 명확해진다.

최적화이론

최적화이론에서 스파스 회귀는 회귀문제에서 해의 스파서티를 최대화하는 것, 다시 말해 $S$ 를 최소화하는 최적화 문제를 말한다.

그래프이론

그래프이론에서 보통 데이터로써 주어지는 랜덤 네트워크의 인접행렬은 스파스 행렬일 것으로 가정한다.

자료구조

실전적인 계산의 영역에서 스파스행렬은 자료구조에 가깝다. 가령 마지막 성분만 $\sqrt{2}$ 이고 나머지는 모두 $0$ 인 $X,Y \in \mathbb{R}^{10^{6} \times 10^{6}}$ 를 생각해보면 이 행렬을 저장하기 위해서는 부동소수점으로 채워진 $2 \cdot 10^{12}$ 칸짜리 배열이 필요한데, 이것이 스파스행렬이라는 정보만 확실하다면 굳이 쓰지도 않을 $0$ 을 다 저장해둘 게 아니라 마지막칸 하나만 있으면 된다. 단순히 저장만 편리한 게 아니라 연산에서도 효율적인데, 이 두 행렬은 어마어마하게 크지만 사실 그 곱은 간단하게도 $$ X Y = \begin{bmatrix} 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 2 \end{bmatrix} $$ 와 같이 구할 수 있다. 이 곱셈을 슈트라센 알고리즘으로 계산했다고 할지라도 그걸 현명하다고 할 수는 없을 것이다. ‘컴퓨터로 스파스행렬을 계산한다’는 것은 이 행렬들을 적은 용량으로 읽고 쓸 수 있으며 그 계산도 $0$ 이 있는 부분은 생략해서 아주 빠르게 수행한다는 뜻이다².