A novel Adaptive weighted Kronecker Compressive Sensing
Recently, multidimensional signal reconstruction using a low number of measurements is of great interest. Therefore, an effective sampling scheme which should acquire the most information of signal using a low number of measurements is required. In this paper, we study a novel cube-based method for sampling and reconstruction of multidimensional signals. First, inspired by the block-based compressive sensing (BCS), we divide a group of pictures (GoP) in a video sequence into cubes. By this way, we can easily store the measurement matrix and also easily can generate the sparsifying basis. The reconstruction process also can be done in parallel. Second, along with the Kronecker structure of the sampling matrix, we design a weight matrix based on the human visuality system, i.e. perceptually. We will also benefit from different weighted $\ell_1$-minimization methods for reconstruction. Furthermore, conventional methods for BCS consider an equal number of samples for all blocks. However, the sparsity order of blocks in natural images could be different and, therefore, a various number of samples could be required for their reconstruction. Motivated by this point, we will adaptively allocate the samples for each cube in a video sequence. Our aim is to show that our simple linear sampling approach can be competitive with the other state-of-the-art methods.% in performance.
Conclusion.tex
%=======================
\section{Discussion and Conclusions}
%=======================

In this paper, we proposed a novel cube-based weighted $\ell_{1}$ minimization algorithm based on HVS for reconstruction of compressible video signals using KCS approach. First, to make the KCS approach practical to use, it is developed to cube-based one which can be processed in parallel and also makes it applicable to any large-size videos. Second, we propose to assign some novel weights to each voxel perceptually based on the quantization matrix of JPEG. Simulation results demonstrated the superiority of our proposed WCS approach. As a future work, we propose to add popular reweighted CS reconstruction methods to further gain the performance. Tensor decomposition could also be used for processing of each cube. This could reduce the reconstruction complexity \cite{friedland2014compressive}. Adaptively allocation of the samples for each cube based on the sparsity order of each cube in video sequence could also be applied. Designing perceptual weights based on the contrast sensitivity function (CSF) for wavelet domain is also another interesting direction of this research.

%Different from other conventional WCS approaches, our method is non-iterative which makes it fast. 
% Fourth, we adaptively allocate the number of samples for each cube based on the sparsity of them. 
Experimens.tex
%=======================
\section{Experiments}
%=======================
We provide some simulations to validate the effectiveness of our algorithm. Different from \cite{duarte2012kronecker}, we assume Gaussian measurement matrix and DCT matrix as a sparsifying basis. First, to investigate the effectiveness of our proposed WCS scheme, we apply it to images. Fig. 1 (a) compares the PSNR of our proposed WCS algorithm with other state-of-the-art methods like iterative reweighted least square (IRLS) \footnote{we have used the MATLAB code provided by the authors and available at: http://www-m15.ma.tum.de/Allgemeines/NewPublications} and, RWL1 \cite{candes2008} method for Lenna test image. Second, we evaluate the proposed cube-based WKCS approach for video sequences. Fig. 1 (b) shows the PSNR for the proposed cube-based approach for the Foreman video sequence. It can be seen that by assigning the weights based on HVS, the performance of KCS is improved. Unlike \cite{duarte2012kronecker}, since we have assumed cube-based KCS, then assumption of dense sensing matrix (i.e. $\mathbf{\Phi}_3$) which improves the performance is reasonable. We also observed that increasing the cube size reduces the blocking artifact and improves the performance, but, the computational complexity is increased. 
%-------------------------------------------------

% All results are reported by averaging 10 independent trials.
%\footnote{we have used the MATLAB code provided by the authors and available at: http://www-m15.ma.tum.de/Allgemeines/NewPublications}
%\footnote{I. Daubechies, R. DeVore, M. Fornasier, and C. S. Gunturk, “Iteratively reweighted least squares minimization for sparse recovery,” Communications on Pure and Applied Mathematics, vol. 63, no. 1, pp. 1–38, 2010.}

%\begin{figure}\label{Fig_KCS}
%  \centering
%  \includegraphics[width=8cm,height=5cm]{PSNR_Lenna.eps}
%  \caption{PSNR vs normalized measurement rate for the Foreman video sequence.}
%  \label{Block_Size}
%\end{figure}

\begin{figure}[t]
\begin{minipage}[b]{.5\linewidth}
  \centering
  \centerline{\includegraphics[width=4.8cm,height=4.5cm]{PSNR_Lenna.eps}}
%  \vspace{1.5cm}
  \centerline{(a)}\medskip
\end{minipage}
\begin{minipage}[b]{0.5\linewidth}
  \centering
  \centerline{\includegraphics[width=4.8cm,height=4.5cm]{Fig_PSNR_KCS_compare.eps}}
%  \vspace{1.5cm}
  \centerline{(b)}\medskip
\end{minipage}
\caption{PSNR vs normalized measurement rate: (a) Proposed WCS approach for the Lenna test image. (b) Proposed cube-based WKCS for the Foreman video sequence.}
\label{Vis}
\end{figure}

%\begin{tabular}{|*{1}{p{70pt}|}*{2}{c|}}
\begin{table}\small 
	\begin{tabular}{|*{1}{p{130pt}|}*{2}{c|}}
		\hline
		Methods&$\Phi$&$\Psi$\\
		\hline
		CS Independent& $\mathbf{I} \otimes \mathbf{\Phi}_s$ & $\mathbf{I} \otimes \mathbf{\Psi}_s$ \\
		\hline
		KCS, Cube-base KCS and WKCS & $\mathbf{I} \otimes \mathbf{\Phi}_s$ & $\mathbf{\Psi}_t \otimes \mathbf{\Psi}_s$\\
		\hline
		Global KCS & $\mathbf{\Phi}_t \otimes \mathbf{\Phi}_s$ & $\mathbf{\Psi}_t \otimes \mathbf{\Psi}_s$\\
		\hline
		Cube-based 3D KCS and WKCS & $\mathbf{\Phi}_3$ & $\mathbf{\Psi}_t \otimes \mathbf{\Psi}_s$\\		
		\hline
	\end{tabular}
	\centering
	\vspace{+0.1cm}
	\normalsize
	\caption{Structure of measurement and sparsifying basis matrices. }
	\label{tab:SynResult}
\end{table}
ICASSP_2017_Forum_include_bibitem.tex
% Template for ICASSP-2017 paper; to be used with:
%          spconf.sty  - ICASSP/ICIP LaTeX style file, and
%          IEEEbib.bst - IEEE bibliography style file.
% --------------------------------------------------------------------------
\documentclass{article}
\usepackage{spconf,amsmath,amssymb,amsbsy,amsxtra,graphicx}
\usepackage{array,multirow}
\usepackage{threeparttable}
\usepackage[ruled]{algorithm2e}
%\usepackage{ocolumn}
\usepackage{booktabs}
\usepackage{url}
\usepackage{cite}
\usepackage{psfrag}
\usepackage{dcolumn}
%\usepackage{adjustbox}
\usepackage{cite}
\usepackage{bm}
\usepackage{subfigure}
\usepackage{verbatim}
\usepackage{colortbl}
\usepackage{algorithmic}
\usepackage{epstopdf}
   

% Example definitions.
\newcommand{\xx}{{\bf x}}

\graphicspath{{./Images/}}
\ninept
%===================================<< Title >>===============================
% Title.
% ------
\title{A novel Adaptive weighted Kronecker Compressive Sensing}
%
% Single address.
% ---------------
\name{Seyed Hamid Safavi, Farah Torkamani-Azar}
\address{Cognitive Communication Research Group, \\Department of Electrical Engineering, \\ Shahid Beheshti University, Tehran, Iran}
%
% For example:
% ------------
%\address{School\\
%	Department\\
%	Address}
%


\begin{document}
%\ninept
%
\maketitle
%
\small    
\input{abstract}
\input{introduction}
\input{ProbFormulation}
\input{Experimens}
\input{Conclusion}


\begin{thebibliography}{1}

\bibitem{donoho}
D.~L.~Donoho,  \emph{Compressed Sensing}, IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289-1306, 2006.

\bibitem{duarte2012kronecker}
M.~F.~Duarte, and R.~G.~Baraniuk, \emph{Kronecker Compressive Sensing}, IEEE Trans. on Image Process., vol. 21, no. 2, pp. 494-504, 2012.

\bibitem{sidiropoulos2012multi}
N.~D.~Sidiropoulos, and A.~Kyrillidis, \emph{Multi-way compressed sensing for sparse low-rank tensors}, IEEE Signal Processing Letters, vol. 19, no. 11, pp. 757-760, 2012.

\bibitem{friedland2014compressive}
S.~Friedland, Q.~Li, and D.~Schonfeld, \emph{Compressive sensing of sparse tensors}, IEEE Trans. on Image Process., vol. 23, no. 10, pp. 4438-4447, 2014.

\bibitem{fowler2012block}
J.~Fowler, S.~Mun, and E.~Tramel, \emph{Block-based compressed sensing of images and video}, Foundations and Trends in Signal Processing, vol. 4, no. 4, pp. 297-416, 2012.

\bibitem{candes2008}
E.~J.~Candes, M.~B.~Wakin, and S.~Boyd, \emph{Enhancing sparsity by reweighted $\ell_1$ minimization}, Journal of Fourier analysis and applications, Springer, vol. 14, no. 5-6, pp. 877-905, 2008.

\bibitem{Safavi2016}
S.~H.~Safavi and F.~Torkamani-Azar, \emph{Sparsity-Aware Adaptive Block-Based Compressive Sensing}, IET Signal Processing,  In press, 2016, DOI:  10.1049/iet-spr.2016.0176.

\end{thebibliography}

%\bibliographystyle{IEEEbib}
%\bibliography{refs}

\end{document}

ProbFormulation.tex
%--------------------------------<< Proposed Approach >>-----------------------------------------%
\section{Proposed Approach}
%In this research, our aim is to overcome some challenges in reconstruction of high-dimensional signals. Cube-based CS is conducted to overcome the problem of storing large size measurement and sparsifying matrices and keeping the recnstruction complexity as low as possible. We apply the KCS approach to better use the intrinsic structure of multidimensional signal. This approach also enables us to reconstruct the whole signal using partitioned measurements. 

%Furthermore, along with the Kronecker structure of sampling matrix and sparsifying matrix, we propose to apply some weights to each voxel perceptualy to improve the performance. Since the RWL1 approach \cite{candes2008} is iterative and it has a higher computational complexity compared to unweighted CS, we try to answer this question: how we could design the \textit{non-iterative} and \textit{image independent} weighting matrix of CS? Motivated by the fact that the human eye is not much sensitive to the high frequency details, we could give an importance to each frequency in signal reconstruction, such that the high frequencies have a small effect on the performance. Hence, we could expect better visuality performance from the proposed scheme compared to other conventional weighted methods. One benefit that could be expected for this approach is the independency of the weighting coefficients from input images which makes it non-iterative and fast.

%Since the RWL1 approach \cite{candes2008} is iterative and it has a higher computational complexity compared to unweighted CS, in this research, we try to answer this question: how we could design the \textit{non-iterative} and \textit{image independent} weighting matrix of CS? Motivated by the fact that the human eye is not much sensitive to the high frequency details, we could give an importance to each frequency in signal reconstruction, such that the high frequencies have a small effect on the performance. Hence, we could expect better visuality performance from the proposed scheme compared to other conventional weighted methods. One benefit that could be expected for this approach is the independency of the weighting coefficients from input images which makes it non-iterative and fast.

Since the RWL1 approach \cite{candes2008} is iterative and it has a higher computational complexity compared to unweighted CS, in this research, we try to answer this question: how we could design the \textit{non-iterative} and \textit{image independent} weighting matrix of CS? Motivated by the human visual system (HVS) which state that the sensitivity of human eye is not same for different frequencies, we could give an importance to each frequency in signal reconstruction. Hence, we could expect better visuality performance from the proposed scheme compared to other state-of-the-art WCS methods. One benefit that could be expected for this approach is that the weighting coefficients are image independent which makes it non-iterative and fast.
%It is known that the JPEG scheme benefits from the $8 \times 8$ standard quantization matrix for DCT components of the luminance (e.g.$\mathbf{Q}$) and chrominance (e.g.$\mathbf{C}$) of image (which is based on the psychovisual thresholding)  to weaken the high frequency details in the image \footnote{https://www.w3.org/Graphics/JPEG/itu-t81.pdf}. %In JPEG algorithm, after quantization, since the data sequence has more zeros, it is encoded using the Huffman coding algorithm. 
%Here, we propose to take advantage from this matrix to design the weighting coefficients. % which makes the image data sequence more sparse. 
%We beleive that perceptual weighting could be resulted in better performance compared to other WCS schemes. Now, let us explain how we design the weighting matrix from the popular JPEG quantization matrix. We choose the weights for each video frame in cubes as follows:
Here, we propose to take advantage from the well-known $8 \times 8$ standard luminance quantization matrix of JPEG scheme \footnote{https://www.w3.org/Graphics/JPEG/itu-t81.pdf} (which is based on the psychovisual thresholding) to design the weighting coefficients. % which makes the image data sequence more sparse. 
Now, let us explain how we design the weighting matrix from the popular JPEG quantization matrix. We choose the inverse of the weights for each video frame in cubes as follows:

%========================================== << EQUATION 7>> =====================================%
\begin{equation}
\label{proposed_weight}
\mathbf{Q'} = \mathbf{D} \mathbf{Q}^T \mathbf{D}, \qquad \mathbf{W}^{-1} = \text{Diag} \left(  \text{vec} \left(  \mathbf{Q'} \right) \right)
\end{equation}
%================================================================
where $\mathbf{Q}$ is the quantization matrix and $\mathbf{D}$ is an anti-diagonal matrix which is used for up-down and left-right flips. Similar to the conventional WCS methods higher weights are assigned to small values of the signal to make the signal sparser. Note that for the higher block-size, we could use interpolation for designing the weights. We develop this weight matrix for each cube in the video signal by repeating this weights along the time dimension. Let us consider the reweighted $\ell_1$-minimization problem for $j$'th cube as follows:
%=============================== << EQUATION   >> =====================================%
%\begin{eqnarray}
%\label{gg}
%\underset{\mathbf{s}\in {{\mathbb{R}}^{N}}}{\mathop{\min }}\,\,\sum\limits_{i=1}^{{N}}{{{w}_{j,i}}\left| {{s}_{j,i}} \right|} \quad \left( {j = 1,...,L} \right)\nonumber\\
%\textmd{s.t.} \,\, \mathbf{y}_j=\bm{\theta}_j \mathbf{s}_j \,\, \qquad \qquad \qquad \qquad
%\end{eqnarray}
\begin{eqnarray}
\label{xx}
\underset{\mathbf{s}\in {{\mathbb{R}}^{N}}}{\mathop{\min }}\,\,{{\left\| {{\mathbf{W}}_j}{\mathbf{s}_j} \right\|}_{{{\ell }_{1}}}} \,\, \textmd{s.t.} \,\, \mathbf{y}_j=\bm{\theta}_j \mathbf{s}_j \quad \left( {j = 1,...,L} \right)
\end{eqnarray}
%=================================================================================%
where ${\mathbf{W}}_j = \mathbf{I}_{GoP} \otimes \mathbf{W}$ and $\bm{\theta}_j$ is defined based on Kronecker product ${\bm{\theta}} = {\mathbf{\Phi}} {\mathbf{\Psi}} = {{\mathbf{\Phi }}_t} {{\mathbf{\Psi}}_t} \otimes {{\mathbf{\Phi }}_s} {{\mathbf{\Psi}}_s} = {\bm{\theta}_t} \otimes {\bm{\theta}_s}$ \cite{duarte2012kronecker}. Here ${\mathbf{\Phi}}$ denotes the sampling matrix and ${\mathbf{\Psi}}$ represents the sparsifying basis.

abstract.tex
\begin{abstract}
Recently, multidimensional signal reconstruction using a low number of measurements is of great interest. Therefore, an effective sampling scheme which should acquire the most information of signal using a low number of measurements is required. In this paper, we study a novel cube-based method for sampling and reconstruction of multidimensional signals. First, inspired by the block-based compressive sensing (BCS), we divide a group of pictures (GoP) in a video sequence into cubes. By this way, we can easily store the measurement matrix and also easily can generate the sparsifying basis. The reconstruction process also can be done in parallel. Second, along with the Kronecker structure of the sampling matrix, we design a weight matrix based on the human visuality system, i.e. perceptually. We will also benefit from different weighted $\ell_1$-minimization methods for reconstruction. Furthermore, conventional methods for BCS consider an equal number of samples for all blocks. However, the sparsity order of blocks in natural images could be different and, therefore, a various number of samples could be required for their reconstruction. Motivated by this point, we will adaptively allocate the samples for each cube in a video sequence. Our aim is to show that our simple linear sampling approach can be competitive with the other state-of-the-art methods.% in performance.
\end{abstract} 

\begin{keywords}
Kronecker Compressive Sensing, Multidimensional Signal Reconstruction, Weighted Compressive sensing.
\end{keywords}
introduction.tex
%=======================
\section{Introduction}\label{Introduction}
%=======================
Recently, there has been a lot of interest to apply the theory of Compressive Sensing (CS)  \cite{donoho} to the high-dimensional signals such as color imaging, video, hyperspectral imaging, and multi sensor networks in a real world. In this trend, designing an efficient sampling matrix and a sparsifying basis is a challengable issue. A very simple and common approach to deal with high-dimensional data is representing them in the form of long vectors. However, this approach has some disadvantages; (a) It is not benefited from the existed correlations (or structures) between different dimensions of the data, (b) It needs high memory to store the sensing matrix and sparsifying basis, (c) The reconstruction process is computationally expensive.

To better use the structure of the multidimensional signal, Kronecker Compressive Sensing (KCS) has been proposed \cite{duarte2012kronecker}. Note that in practice, it is difficult to have global measurements of a multidimensional signal, but, partitioned measurements are available which depend only on a subset of the multidimensional signal like distributed sensor networks \cite{duarte2012kronecker}. It is also shown that the signals are more compressible in Kronecker basis than isotropic basis. Despite the valuable benefits of KCS, it has high reconstruction computational complexity for very high-dimensional data which makes it not suitable in practice. There are also some works that use tensor decomposition for designing the sparsifying basis and measurement matrix \cite{sidiropoulos2012multi, friedland2014compressive}. In \cite{sidiropoulos2012multi}, an approach called Multi-Way Compressed Sensing (MWCS) was proposed in which the CS ideas is generalized from the linear to the multi-linear case. Moreover, Generalized Tensor Compressive Sensing (GTCS) is another approach which preserves the intrinsic structure of the tensor data \cite{friedland2014compressive}. However, all of the aforementioned approaches are computationally complex compared to multidimensional approaches based on BCS.

The idea of BCS is to overcome some challenges of high-dimensional signals reconstruction \cite{fowler2012block} such as huge memory requirement to store the large-size measurement matrices and computationally expensive reconstruction process. In conventional CS methods, all frequencies of the image have the same importance. Reweighted $\ell_1$-minimization (RWL1) approach \cite{candes2008} has been proposed to enhance the sparsity by adding some weights to the signal entries. We believe that weighted compressive sensing (WCS) is a powerful method to improve the efficiency of KCS approach. The WCS approach of \cite{candes2008} utilizes an iterative algorithm to determine weights as a function of the reconstructed signal in the previous iteration. Practically the $\ell_1$-norm is replaced by log-sum penalty. In this research, motivated by the structure of the human eye, we propose to give different levels of importance to different entries of a signal in transformed domain. Since the sensitivity of human eye is not same for all frequencies, we can greatly improve the performance by assigning importance to each entries of a signal. In contrast to RWL1 approach \cite{candes2008}, since our scheme of obtaining the weights is not iterative, it could be different and much more efficient in terms of computational complexity.


%\subsection{Contributios}
To summarize, our contribution in this research is twofold: (1) First, to make the KCS approach practical to use, it is developed to cube-based one which can be processed in parallel;
(2) Second, we propose to assign some novel perceptual weights to each voxel.
We also expect the following contributions could improve the performance incredibly:
(1) We will add popular reweighted CS reconstruction methods to further gain the performance;
(2) It is well known that a priori knowledge on sparsity order of signal is not available in practice. Therefore, the upper bound on sparsity order is used. However, the necessary number of samples might be smaller than the obtained upper bound. Hence, as our future work, we can allocate a distinct number of samples for each cube \cite{Safavi2016}.
%Hence, as our last contribution, we propose to allocate a distinct number of samples for each cube \cite{Safavi2016}.
%We will adaptively allocate the number of samples for each cube based on the sparsity of them \cite{Safavi2016}. 


1612.01113.extracted_bib
{donoho D.~L.~Donoho, Compressed Sensing, IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289-1306, 2006.
1612.01113.extracted_bib
{duarte2012kronecker M.~F.~Duarte, and R.~G.~Baraniuk, Kronecker Compressive Sensing, IEEE Trans. on Image Process., vol. 21, no. 2, pp. 494-504, 2012.
1612.01113.extracted_bib
{sidiropoulos2012multi N.~D.~Sidiropoulos, and A.~Kyrillidis, Multi-way compressed sensing for sparse low-rank tensors, IEEE Signal Processing Letters, vol. 19, no. 11, pp. 757-760, 2012.
1612.01113.extracted_bib
{friedland2014compressive S.~Friedland, Q.~Li, and D.~Schonfeld, Compressive sensing of sparse tensors, IEEE Trans. on Image Process., vol. 23, no. 10, pp. 4438-4447, 2014.
1612.01113.extracted_bib
{fowler2012block J.~Fowler, S.~Mun, and E.~Tramel, Block-based compressed sensing of images and video, Foundations and Trends in Signal Processing, vol. 4, no. 4, pp. 297-416, 2012.
1612.01113.extracted_bib
{candes2008 E.~J.~Candes, M.~B.~Wakin, and S.~Boyd, Enhancing sparsity by reweighted $\ell_1$ minimization, Journal of Fourier analysis and applications, Springer, vol. 14, no. 5-6, pp. 877-905, 2008.
1612.01113.extracted_bib
{Safavi2016 S.~H.~Safavi and F.~Torkamani-Azar, Sparsity-Aware Adaptive Block-Based Compressive Sensing, IET Signal Processing, In press, 2016, DOI: 10.1049/iet-spr.2016.0176.