Range Analysis of Matrix Factorization Algorithms for an Overflow Free Fixed-point Design

We consider the problem of enabling robust range estimation of matrix factorization algorithms like eigenvalue decomposition (EVD) algorithm and singular value decomposition (SVD) for a reliable fixed-point design. The simplicity of fixed-point circuitry has always been so tempting to implement EVD algorithms in fixed-point arithmetic. Working towards an effective fixed-point design, integer bit-width allocation is a significant step which has a crucial impact on accuracy and hardware efficiency. This paper investigates the shortcomings of the existing range estimation methods while deriving bounds for the variables of the EVD algorithm. In light of the circumstances, we introduce a range estimation approach based on vector and matrix norm properties together with a scaling procedure that maintains all the assets of an analytical method. The method could derive robust and tight bounds for the variables of EVD and SVD algorithm. The bounds derived using the proposed approach remain same for any input matrix and are also independent of the number of iterations or size of the problem. It was found that by the proposed range estimation approach, all the variables generated during the computation of EVD and SVD algorithms are bounded within +/- 1. We also tried to contemplate the effect of different kinds of scaling factors on the bounds of the variables. Some benchmark hyperspectral data sets have been used to evaluate the efficiency of the proposed technique.