This dissertation reviews the theory of fast matrix multiplication from a multilinear-algebraic point of view, as well as recent fast matrix multiplication algorithms based on discrete Fourier transforms over nite groups. To this end, the algebraic approach is described in terms of group algebras over groups satisfying the triple product Property, and the construction of such groups via uniquely solvable puzzles. The higher order singular value decomposition is an important decomposition of tensors that retains some of the properties of the singular value decomposition of matrices. However, we have proven a novel negative result which demonstrates that the higher order singular value decomposition yields a matrix multiplication algorithm that is no better than the standard algorithm. / Mathematical Sciences / M. Sc. (Applied Mathematics)

Video is a sequence of 2D images of the 3D world generated by a camera. As the camera moves relative to the real scene and elements of that scene themselves move, correlated frame-to-frame changes in the video images are induced. Humans easily identify such changes as scene motion and can readily assess attempts to quantify it. For a machine, the identification of the 2D frame-to-frame motion is difficult. This problem is addressed by the computer vision process of tracking. Tracking underpins the solution to the problem of augmenting general video sequences with artificial imagery, a staple task in the visual effects industry. The problem is difficult because tracking in general video sequences is complicated by the presence of non-rigid motion, repeated texture and arbitrary occlusions. Existing methods provide solutions that rely on imposing limitations on the scenes that can be processed or that rely on human artistry and hard work. I introduce new paradigms, frameworks and algorithms for overcoming the challenges of processing general video and thus provide solutions that fill the gap between the `automated' and `manual' approaches. The work is easily sectioned into three parts, which can be considered separately or taken together for dealing with video without limitations. The initial focus is on directly addressing practical issues of human interaction in the tracking process: a new solution is developed by explicitly incorporating the user into an interactive algorithm. It is a novel tracking system based on fast full-frame patch searching and high-speed optimal track determination. This approach makes only minimal assumptions about motion and appearance, making it suitable for the widest variety of input video. I detail an implementation of the new system using k-d trees and dynamic programming. The second distinct contribution is an important extension to tracking algorithms in general. It can be noted that existing tracking algorithms occupy a spectrum in their use of global motion information. Local methods are easily confused by occlusions, repeated texture and image noise. Global motion models offer strong predictions to see through these difficulties and have been used in restricted circumstances, but are defeated by scenes containing independently moving objects or modest levels of non-rigid motion. I present a well principled way of combining local and global models to improve tracking, especially in these highly problematic cases. By viewing rank-constrained tracking as a probabilistic model of 2D tracks instead of 3D motion, I show how one can obtain a robust motion prior that can be easily incorporated in any existing tracking algorithm. The development of the global motion prior is based on rank-constrained factorization of measurement matrices. A common difficulty comes from the frequent occurrence of occlusions in video, which means that the relevant matrices are often not complete due to missing data. This defeats standard factorization algorithms. To fully explain and understand the algorithmic complexities of factorization in this practical context, I present a common notation for the direct comparison of existing algorithms and propose a new family of hybrid approaches that combine the superb initial performance of alternation methods with the convergence power of the Newton algorithm. Together, these investigations provide a wide-ranging, yet coherent exploration of tracking non-rigid objects in video.

In order to identify the weakest bus in a power system so that the Unified Power Flow Controller could be connected, an investigation of static and dynamic voltage stability is presented. Two stability indices, static and dynamic, have been proposed in the thesis. Multi-Input Multi-Output (MIMO) analysis has been used for the dynamic stability analysis. Results based on the Western System Coordinate Council (WSCC) 3-machine, 9-bus test system and IEEE 14 bus Reliability Test System (RTS) shows that these indices detect with the degree of accuracy the weakest bus, the weakest line and the voltage stability margin in the test system before suffering from voltage collapse. Recently, Flexible Alternating Current Transmission systems (FACTs) have become significant due to the need to strengthen existing power systems. The UPFC has been identified in literature as the most comprehensive and complex FACTs equipment that has emerged for the control and optimization of power flow in AC transmission systems. Significant research has been done on the UPFC. However, the extent of UPFC capability, connected to the weakest bus in maintaining the power flows under fault conditions, not only in the line where it is installed, but also in adjacent parallel lines, remains to be studied. In the literature, it has normally been assumed the UPFC is disconnected during a fault period. In this investigation it has been shown that fault conditions can affect the UPFC significantly, even if it occurred on far buses of the power system. This forms the main contribution presented in this thesis. The impact of UPFC in minimizing the disturbances in voltages, currents and power flows under fault conditions are investigated. The WSCC 3-machine, 9-bus test system is used to investigate the effect of an unsymmetrical fault type and position on the operation of UPFC controller in accordance to the G59 protection, stability and regulation. Results show that it is necessary to disconnect the UPFC controller from the power system during unsymmetrical fault conditions.

Gowers, dans son article sur les matrices quasi-aléatoires, étudie la question, posée par Babai et Sos, de l'existence d'une constante $c>0$ telle que tout groupe fini possède un sous-ensemble sans produit de taille supérieure ou égale a $c|G|$. En prouvant que, pour tout nombre premier $p$ assez grand, le groupe $PSL_2(\mathbb{F}_p)$ (d'ordre noté $n$) ne posséde aucun sous-ensemble sans produit de taille $c n^{8/9}$, il y répond par la négative. Nous allons considérer le probléme dans le cas des groupes compacts finis, et plus particuliérement des groupes profinis $SL_k(\mathbb{Z}_p)$ et $Sp_{2k}(\mathbb{Z}_p)$. La premiére partie de cette thése est dédiée à l'obtention de bornes inférieures et supérieures exponentielles pour la mesure suprémale des ensembles sans produit. La preuve nécessite d'établir préalablement une borne inférieure sur la dimension des représentations non-triviales des groupes finis $SL_k(\mathbb{Z}/(p^n\mathbb{Z}))$ et $Sp_{2k}(\mathbb{Z}/(p^n\mathbb{Z}))$. Notre théoréme prolonge le travail de Landazuri et Seitz, qui considérent le degré minimal des représentations pour les groupes de Chevalley sur les corps finis, tout en offrant une preuve plus simple que la leur. La seconde partie de la thése à trait à la théorie algébrique des nombres. Un polynome monogéne $f$ est un polynome unitaire irréductible à coefficients entiers qui endengre un corps de nombres monogéne. Pour un nombre premier $q$ donné, nous allons montrer, en utilisant le théoréme de densité de Tchebotariov, que la densité des nombres premiers $p$ tels que $t^q -p$ soit monogéne est supérieure ou égale à $(q-1)/q$. Nous allons également démontrer que, quand $q=3$, la densité des nombres premiers $p$ tels que $\mathbb{Q}(\sqrt[3]{p})$ soit non monogéne est supérieure ou égale à $1/9$. / Gowers in his paper on quasirandom groups studies a question of Babai and Sos asking whether there exists a constant $c > 0$ such that every finite group $G$ has a product-free subset of size at least $c|G|$. Answering the question negatively, he proves that for sufficiently large prime $p$, the group $\mathrm{PSL}_2(\mathbb{F}_p)$ has no product-free subset of size $\geq cn^{8/9}$, where $n$ is the order of $\mathrm{PSL}_2(\mathbb{F}_p)$. We will consider the problem for compact groups and in particular for the profinite groups $\SL_k(\mathh{Z}_p)$ and $\Sp_{2k}(\mathbb{Z}_p)$. In Part I of this thesis, we obtain lower and upper exponential bounds for the supremal measure of the product-free sets. The proof involves establishing a lower bound for the dimension of non-trivial representations of the finite groups $\SL_k(\mathbb{Z}/(p^n\mathbb{Z}))$ and $\Sp_{2k}(\mathbb{Z}/(p^n\mathbb{Z}))$. Indeed, our theorem extends and simplifies previous work of Landazuri and Seitz, where they consider the minimal degree of representations for Chevalley groups over a finite field. In Part II of this thesis, we move to algebraic number theory. A monogenic polynomial $f$ is a monic irreducible polynomial with integer coefficients which produces a monogenic number field. For a given prime $q$, using the Chebotarev density theorem, we will show the density of primes $p$, such that $t^q-p$ is monogenic, is greater than or equal to $(q-1)/q$. We will also prove that, when $q=3$, the density of primes $p$, which $\mathbb{Q}(\sqrt[3]{p})$ is non-monogenic, is at least $1/9$.

Student Number : 8315331 - MSc dissertation - School of Electrical and Information Engineering - Faculty of Engineering and the Built Environment / In this dissertation an efficient algorithm to calculate the differential of the network output with respect to its inputs is derived for axis orthogonal Local Model (LMN) and Radial Basis Function (RBF) Networks. A new recursive Singular Value Decomposition (SVD) adaptation algorithm, which attempts to circumvent many of the problems found in existing recursive adaptation algorithms, is also derived. Code listings and simulations are presented to demonstrate how the algorithms may be used in on-line adaptive neurocontrol systems. Specifically, the control techniques known as series inverse neural control and instantaneous linearization are highlighted. The presented material illustrates how the approach enhances the flexibility of LMN networks making them suitable for use in both direct and indirect adaptive control methods. By incorporating this ability into LMN networks an important characteristic of Multi Layer Perceptron (MLP) networks is obtained whilst retaining the desirable properties of the RBF and LMN approach.

傳統的主成分分析(principal component analysis)法，只能分析二式二向的資料(2-mode 2-way data)，若是要處裡三向三式的資料(3-mode 3-way data)或是更多維的資料，則必須用其它的方法。例如將某一向資料取平均數，再做分析。此法雖然可行，但卻忽略三向資料間可能潛藏的相關性。且社會科學的研究日趨複雜，三向資料也就更常見到，而我們可能也對三向資料間彼此的關聯感到興趣。因此在1960、1970年代，學者開始研究將主成分分析的模型加以擴展成適合分析三向資料的模型。本文除了介紹三向資料主成分分析所使用的Tucker3模型及其參數估計法外，也以28家股票上市公司為實例，探討資本結構影響因素於五年間（1989~1993年）在不同公司群組間的變化情形。

<p>In computational science it is common to describe dynamic systems by mathematical models in forms of differential or integral equations. These models may contain parameters that have to be computed for the model to be complete. For the special type of ordinary differential equations studied in this thesis, the resulting parameter estimation problem is a separable nonlinear least squares problem with equality constraints. This problem can be solved by iteration, but due to complicated computations of derivatives and the existence of several local minima, so called short-cut methods may be an alternative. These methods are based on simplified versions of the original problem. An algorithm, called the modified Kaufman algorithm, is proposed and it takes the separability into account. Moreover, different kinds of discretizations and formulations of the optimization problem are discussed as well as the effect of ill-conditioning.</p><p>Computation of parameters often includes as a part solution of linear system of equations <i>Ax = b</i>. The corresponding pseudoinverse solution depends on the properties of the matrix <i>A</i> and vector <i>b</i>. The singular value decomposition of <i>A</i> can then be used to construct error propagation matrices and by use of these it is possible to investigate how changes in the input data affect the solution <i>x</i>. Theoretical error bounds based on condition numbers indicate the worst case but the use of experimental error analysis makes it possible to also have information about the effect of a more limited amount of perturbations and in that sense be more realistic. It is shown how the effect of perturbations can be analyzed by a semi-experimental analysis. The analysis combines the theory of the error propagation matrices with an experimental error analysis based on randomly generated perturbations that takes the structure of <i>A</i> into account</p>

In computational science it is common to describe dynamic systems by mathematical models in forms of differential or integral equations. These models may contain parameters that have to be computed for the model to be complete. For the special type of ordinary differential equations studied in this thesis, the resulting parameter estimation problem is a separable nonlinear least squares problem with equality constraints. This problem can be solved by iteration, but due to complicated computations of derivatives and the existence of several local minima, so called short-cut methods may be an alternative. These methods are based on simplified versions of the original problem. An algorithm, called the modified Kaufman algorithm, is proposed and it takes the separability into account. Moreover, different kinds of discretizations and formulations of the optimization problem are discussed as well as the effect of ill-conditioning. Computation of parameters often includes as a part solution of linear system of equations Ax = b. The corresponding pseudoinverse solution depends on the properties of the matrix A and vector b. The singular value decomposition of A can then be used to construct error propagation matrices and by use of these it is possible to investigate how changes in the input data affect the solution x. Theoretical error bounds based on condition numbers indicate the worst case but the use of experimental error analysis makes it possible to also have information about the effect of a more limited amount of perturbations and in that sense be more realistic. It is shown how the effect of perturbations can be analyzed by a semi-experimental analysis. The analysis combines the theory of the error propagation matrices with an experimental error analysis based on randomly generated perturbations that takes the structure of A into account

現今許多網路商店或電子商務將產品銷售給消費者的過程中，皆使用推薦系統的幫助來提高銷售量。如亞馬遜公司(Amazon)、Netflix，深入了解顧客的使用習慣，建構專屬的推薦系統並進行個性化的推薦商品給每一位顧客。 推薦系統應用的技術分為協同過濾和內容過濾兩大類，本研究旨在探討協同過濾推薦系統中潛在因子模型方法，利用矩陣分解法找出評分矩陣。在Koren等人(2009)中，將矩陣分解法的演算法大致分為兩種，隨機梯度下降法(Stochastic gradient descent)與交替最小平方法(Alternating least squares)。本研究主要研究目的有三項，一為比較交替最小平方法與隨機梯度下降法的預測能力，二為兩種矩陣分解演算法在加入偏誤項後的表現，三為先完成交替最小平方法與隨機梯度下降法，以其預測值對原始資料之遺失值進行資料插補，再利用奇異值分解法對完整資料做矩陣分解，觀察其前後方法的差異。 研究結果顯示，隨機梯度下降法所需的運算時間比交替最小平方法所需的運算時間少。另外，完成兩種矩陣分解演算法後，將預測值插補遺失值，進行奇異值分解的結果也顯示預測能力有提升。 / Recommender system has been largely used by Internet companies such Amazon and Netflix to make recommendations for Internet users. Techniques for recommender systems can be divided into content filtering approach and collaborative filtering approach. Matrix factorization is a popular method for collaborative filtering approach. It minimizes the object function through stochastic gradient descent and alternating least squares. This thesis has three goals. First, we compare the alternating least squares method and stochastic gradient descent method. Secondly, we compare the performance of matrix factorization method with and without the bias term. Thirdly, we combine singular value decomposition and matrix factorization. As expected, we found the stochastic gradient descent takes less time than the alternating least squares method, and the the matrix factorization method with bias term gives more accurate prediction. We also found that combining singular value decomposition with matrix factorization can improve the predictive accuracy.

奇異值分解(singular valve decomposition)是一個重要且被廣為運用的矩陣分解方法，其具備許多良好性質，包括低階近似理論(low rank approximation)。在現今大數據(big data)的年代，人們接收到的資訊數量龐大且形式多元。相較於文字型態的資料，影像資料可以提供更多的資訊，因此影像資料扮演舉足輕重的角色。影像資料的儲存比文字資料更為複雜，若能運用影像壓縮的技術，減少影像資料中較不重要的資訊，降低影像的儲存空間，便能大幅提升影像處理工作的效率。另一方面，有時影像在被存取的過程中遭到雜訊汙染，產生模糊影像，此模糊的影像被稱為退化影像(image degradation)。近年來奇異值分解常被用於解決影像處理問題，對於影像資料也有充分的解釋能力。本文考慮將奇異值分解應用在影像壓縮與去除雜訊上，以奇異值累積比重作為選取奇異值的準則，並透過模擬實驗來評估此方法的效果。 / Singular value decomposition (SVD) is a robust and reliable matrix decomposition method. It has many attractive properties, such as the low rank approximation. In the era of big data, numerous data are generated rapidly. Offering attractive visual effect and important information, image becomes a common and useful type of data. Recently, SVD has been utilized in several image process and analysis problems. This research focuses on the problems of image compression and image denoise for restoration. We propose to apply the SVD method to capture the main signal image subspace for an efficient image compression, and to screen out the noise image subspace for image restoration. Simulations are conducted to investigate the proposed method. We find that the SVD method has satisfactory results for image compression. However, in image denoising, the performance of the SVD method varies depending on the original image, the noise added and the threshold used.