This study considers different approaches to calculating the first singular value of the Singular Value Decomposition (SVD) transform. The SVD is closely associated with several common matrix norms and offers an efficient method for their computation. Sum first k singular values called the Ky Fan k-norm. In our approach, the Ky Fan norm is a fragment descriptor. There is no need to do a complete SVD transformation to obtain the norm value. It is enough to obtain a matrix of singular values. In video fragment analysis, the number of fragments and their size significantly affect the calculation speed. The SVD method is robust but does not necessarily scale well to larger matrices. Thus, to use SVD in a practical sense with large datasets, we needed a faster algorithm that finds the same dominant patterns as regular SVD but with only a fraction of the computational cost. We compare the effectiveness of alternative approaches depending on the size of the fragments and their number.
There has been significant interest in the Singular Value Decomposition (SVD) algorithm over the
last few years because of its wide applicability in multiple fields of science and engineering, both
standalone and as part of other computing methods. The singular value decomposition is the most
common and valuable decomposition in computer vision [
We focused on video fragment processing, and in our approach, we consider fragments to be
geometric parts of video frames, represented as matrices with arbitrary dimensions. The research
[
In the study [
The SVD transformation is applied to each fragment, and the first singular value is chosen as the fragment descriptor. If we divide the frame into 5x5, then we need to calculate 25 matrices of a certain size. Increasing the number of fragments will lead to a decrease in the size of the input 1International Workshop on Computational Intelligence, co-located with the IV International Scientific Symposium “Intelligent Solutions” (IntSol-2025), May 01-05, 2025, Kyiv-Uzhhorod, Ukraine sergii.mashtalir@nure.ua (S. Mashtalir); dmytro.lendel@uzhnu.edu.ua (D. Lendel) 0000-0002-0917-6622 (S. Mashtalir); 0000-0003-3971-1945 (D. Lendel)
© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). matrices, but the number of SVD applications will increase. Considering the number of transformations, optimization of the calculation process comes to the fore.
The process of Singular Value Decomposition (SVD) [
where U is an m×m complex unitary matrix, Σ is an m×n diagonal matrix with non-negative real numbers on the diagonal, and V is an n×n complex unitary matrix. If A is real, U and V can be guaranteed to be also real orthogonal matrices. The singular values (σ i) describe the "energy" or importance of each corresponding dimension in the matrix. This computation allows us to retain the important singular values that the image requires while also releasing the values that are not as necessary in retaining the quality of the image. The singular values of an m × n matrix A are the square roots of the eigenvalues of the n × n matrix AT A, which are typically organized by magnitude in decreasing order. Before we apply the SVD to image processing, we will first demonstrate the method using a small (2×3) matrix A:
A =U Σ V t,
A =[ 42 53 76] and then follow a step-by-step process to rewrite the matrix A in the separated form U Σ V t : [ 22 20 40 AT A, we need to compute the determinant of the matrix AT A − λI . In general, we compute the determinant of a 3 × 3 matrix in the following way: [dh ei fj ]=a|he fi|−d|bh ci|+ g|be cf|=a ( ej−hf )+ d ( bi−hc )+ d ( bf −ec ) a b c
We could extend this computation to an n × n matrix as needed. For our example, we compute the determinant of AT A − λI which is:
we solve the characteristic equation for λ, and here we see that λ = 0, 4.3444, 134.6556. We reorder the eigenvalues in decreasing magnitude, so that: λ1=134.6556 , λ2=4.3444 λ3=0. 0. The singular values of are defined as the square roots of the eigenvalues: σ 1=√134.6556 ≈ 11.6041 , σ 2=√ 4.344 ≈ 2.0843 , σ 3=√0=0 (6)
To determine the matrix Σ, we list the non-zero singular values, σ i, in decreasing magnitude down the main diagonal of Σ, where σ i=√ λi. Then, we add any additional rows and columns of zeros as needed to retain the original dimension of A in Σ. In our example, we have three singular values: 11.6041, 2.0843 and 0. We only need to retain the non-zero values, and hence, we form the matrix:
Next, find eigenvectors (columns of ). The eigenvectors 1, 2 are determined from the equation where λ1=134.67:
We have two singular values in our example, and we use them to form the following vectors: ( A AT − λI ) u=0, [7645−134.67 65 x 1 ]=[0] 65−137.67 ][ y 1 0 u 1=( 11..40675163 , 1.41656 )=( 0.7311,0 .6823 ) (7) (8) (9) (10) (11) (12) (13) (14) Similarly for λ2=4.33:
Next, we need find matrixV. The eigenvectors 1,2, 3 are determined from the equation: Solving the equation for each eigenvalue, we obtain the normalized eigenvectors:
Now, we understand the complexity of the SVD calculation. We can explore different
calculating approaches since we are only interested in the first singular value. The simplest
solution would be to stop the calculation as soon as the first singular value is found. Moreover, we
do not need the matrices U and V. This will be an incomplete SVD. Numpy library is the proposed
parameter “full_matrices” in linalg.svd function. We can set full_matrices =False and hope to find
singular value without full calculation. However, if the dimension of the input matrix is large, this
approach may not give the desired result.
2.2. UTV, ULV
The SVD method is robust but does not necessarily scale well to larger matrices. Thus, to use SVD
in a practical sense with large datasets, we needed a faster algorithm that finds the same dominant
patterns as regular SVD, but with only a fraction of the computational cost. In search of an
alternative approach it would be logical to pay attention on UTV and ULV decomposition. UTV
decomposition [
A =UT V t (15)
Where U and V are orthogonal matrices (similar to SVD). T is an upper triangular matrix, unlike the diagonal Σ in SVD. This method is often used as a more efficient alternative to SVD in applications where exact singular values are not required, but a good approximation is sufficient. UTV factorization begins by applying a series of Householder reflections or randomized projections to transform the given matrix A into an upper triangular or upper trapezoidal matrix T while preserving its dominant numerical properties. This transformation ensures that most of the essential information in A is retained while simplifying its structure. The process involves computing orthogonal matrices U and V at capture the column and row spaces of A, respectively, mapping it into the triangular form. Once the factorization is complete, the result is a decomposition A =UT V t, where T serves as a computationally efficient approximation of the singular structure of A, similar to Σ in SVD but with a triangular shape.
ULV factorization [
A =UL V t (16) which serves as a computationally efficient alternative to SVD, particularly in cases where structured rank-revealing decompositions are beneficial.
ULV and UTV are providing full SVD, decomposition and Lanczos SVD [
A bk ‖A bk‖
First, we multiply b0 to compute the matrix-vector product A ( A bk) and divide the result with the norm (|‖A bk‖). We will continue until the result has converged, in other words, when the difference between iterations is below a defined threshold. The power method has a few assumptions: b0 has a non-zero component in the direction of an eigenvector associated with the dominant eigenvalue. Initializing b₀ randomly minimizes the possibility that this assumption is not fulfilled, and matrix A has a dominant eigenvalue that must be greater in magnitude than other eigenvalues. These assumptions guarantee that the algorithm converges to a reasonable result. The smaller the difference between the dominant eigenvalue and the second eigenvalue, the longer it might take to converge. dominant singular values efficiently, whereas UTV is more general in preserving an uppertriangular structure. Lanczos SVD, in contrast, uses an iterative Krylov subspace approach to build a bidiagonal matrix rather than a strict lower triangular matrix. Given that full SVD is computationally expensive, we now turn to Power SVD and Randomized SVD, which efficiently approximate dominant singular values without performing a complete decomposition.
Power iteration [
A promising approach for efficient singular value decomposition is Randomized SVD [
Now, Y is an k by n matrix and we are computing SVD on a matrix with a column size of k rather than m, which should be much less computational cost if we choose a small k.
U Y ∑Y V Y¿ ← SVD ( Y )
Z = AP
t
Y =Q A
Q , R ← QR Factorization ( Z )
This reduces the column space of A while preserving its dominant features, decreasing the dimensionality from n to k (matching the row dimension of P). However, with high probability, Z will still retain the most significant column space features of A. QR factorization of Z provides an orthonormal basis Q, which captures the dominant column space of A:
U =Q U Y (22) This step extends U yback to the original column dimension of A.
We are ready to compare the approaches, evaluate their accuracy in calculating the first singular value and speed in the fragment analysis contest.
In this section, we will consider the results produced by the developed application. Our experiment used a surveillance camera source Figure 3. Codec is h264, frame size is 1280 x 720. To visualize the results of utilizing the Ky Fan norm for video analysis, a Python 3.10.11 application was developed and executed on a system equipped with an Intel Core i5 processor, 16 GB of RAM, and running the Windows operating system. The application relies on two open-source libraries licensed under Apache License: OpenCV version 4.10.0 and NumPy version 2.2.1. Frames are converted from RGB to a grayscale model. Each frame is divided into smaller fragments through a grid-based segmentation technique.
Before evaluating the speed of the selected approaches, we need to check the accuracy of finding the first singular value for different fragment sizes. The results are presented in Table 1. All approaches: SVD, incomplete SVD, Power iteration, UTL, Lanczos SVD and Randomized SVD show same singular values for different fragment sizes. The ULV approach showed no significant deviation. This deviation may be because ULV does not explicitly compute singular values like SVD-based methods, so minor deviations are expected. If high precision for singular values is required, ULV may not be the best choice—methods like Power SVD, Lanczos SVD, and Randomized SVD are preferable. However, if the goal is structured decomposition or efficient matrix transformation, ULV remains a valuable alternative.
All approaches exclude ULV 31541.411066 572.544123
We compared the average calculation time for fragments of different sizes. The results are presented on Figure 4. Methods with full decomposition showed the longest time for fragments of high dimension. Methods optimized for finding the first singular value showed the best time.
The best optimized approach Power SVD for different fragment sizes. The best result is marked in blue, the worst in red in Table 2.
The total processing time of the entire frame using different methods is presented in Figure 5. If the frame is divided into 5x5, then the transformation should be applied to 25 matrices of size 144x256, with a division into 50x50 there will be 250 matrices of size 14x25. The speed is chosen as average, therefore the processing speed of each fragment depends on the sparsity of the matrix. Randomize SVD performed the worst on small matrices. This approach was designed for highdimensional matrices and is not efficient for low-dimensional matrices. Approaches using full decomposition are quite slow on both small and large matrices.
The best optimized approach Power SVD for different fragment sizes. The best result is marked in blue, the worst in red in Table 3. Conclusions Video fragment analysis involves dividing the frame into geometric regions of different sizes depending on the task. For motion detection, dividing the frame into 5x5 or 10x10 is enough to determine the area of interest. That is, find the part of the frame where the movement occurs. Of course, the object's size must be smaller than the size of the fragment. To determine the contours of the object, we must increase the scale. And as a result, we will get several high-order matrices or many low-order matrices. It should also be noted that on fragments of small sizes, but with a large number of fragments themselves, the worst results were shown by Randomized SVD . At the same time, with the increase in fragment sizes, the performance of the UTV and ULV algorithms has deteriorated, so they are the worst solution for motion detection. For practical real-time video analysis, the Power SVD is best suited. For offline analysis, all algorithms will be pretty effective.
The authors have not employed any Generative AI tools.