Finding Subsampling Index Sets for Kronecker Product of Unitary Matrices for Incoherent Tight Frames

Abstract

공간 생성을 위한 기저의 개수보다 더 많은 벡터들을 가질 수 있는 frame은 양자물리, 그래프 이론, 희소 신호 처리, 그리고 대수 기하학에서 그 중요성을 인정받았다. 특히, frame이 가지는 벡터들이 서로 일관성이 낮은 incoherent frame은 많은 분야에서 필요로 하는 frame의 종류이다. 그러나 낮은 일관성 및 벡터의 길이를 유지하며 frame 내의 벡터 수를 늘리는 것은 어려운 문제이다. 본 논문에서는 유니터리 행렬와 푸리에 행렬을 크로네커 곱 한 행렬에서 행 인덱스들을 선택함으로써 incoherent tight frame을 설계한다. 크로네커 곱은 유니터리 행렬을 이용하여 푸리에 행렬을 블록 단위로 가지는 행렬을 생성함으로써 적은 수의 위상을 유지하며 큰 차원을 갖는 frame을 설계할 수 있도록 한다. 또한, 유니터리 행렬로서 하다마드 행렬을 채택하게 되면 일관성 측정을 위한 Gram 행렬의 계산에서 계산 복잡도를 효과적으로 낮출 수 있다. 실험 결과를 통해 더 많은 수의 위상을 가지는 기존의 harmonic frame과 우리가 설계한 frame이 coherence 면에서 차이가 없으며, 이는 적은 수의 위상으로도 많은 수의 위상을 가지는 harmonic frame의 성능을 낼 수 있음을 보인다. 그리고 여러 차원의 frame을 설계해봄으로써 이론적으로 가장 낮은 일관성을 갖는 equiangular tight frame을 발견하였다. 더하여, 압축 센싱 분야에 적용하여 간단한 통신 시스템에 적용한 결과에서 본 논문이 제시하는 방법으로 설계한 frame이 비교적 높은 사용자 활성도에서 기존의 harmonic frame보다 좋은 성능을 냄을 확인하였다.|Frames are recognized for their importance in many fields of communications, sparse signal processing, graph theory, quantum physics, and so on. The low mutual coherence of a frame means low similarity between frame vectors, which is the desired property in many applications. The Gram matrix of the frame is usually used to obtain the mutual coherence. In general, increasing the number of vectors in a frame while maintaining low mutual coherence at the same length is a challenging task. In this paper, we design an incoherent tight frame by selecting the indices of a matrix that is the Kronecker product of Fourier and unitary matrices. The Kronecker product based frame allows its element to have small phase, regardless of the frame length, which is suitable for low cost implementation. We derive an objective function by transforming the Gram matrix expression to compute the mutual coherence of the Kronecker product based frames. We deploy the Hadamard matrix as a unitary matrix to reduce the computational complexity in the derived objective function calculation. We show that solving this objective function has lower computational complexity than conventional Gram matrix computations. We apply this objective function in an optimization problem of finding subsampling index sets for low mutual coherence, and solve this problem by existing algorithms. In simulation, we show that the Kronecker product based frames which require lower implementation complexity due to the small number of phases can achieve similar mutual coherence to the harmonic frames. We apply the frames to compressed sensing (CS) as the measurement matrices to recover the sparse signals and show that the designed incoherent tight frames perform well.