A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Doctor of Philosophy / In this thesis we used the following four types of optimal control problems: (i) Problems governed by systems of ordinary differential equations; (ii) Problems governed by systems of ordinary differential equations with time-delayed arguments appearing in both the state and the control variables; (iii) Problems governed by linear systems subject to sudden jumps in parameter values; (iv) A chemical reactor problem governed by a couple of nonlinear diffusion equations. • The aim of this thesis is to devise computational algorithms for solving the optimal control problems under consideration. However, our main emphasis are on the mathematical theory underlying the techniques, the convergence properties of the algorithms and the efficiency of the algorithms. Chapters II and III deal with problems of the first type, Chapters IV and V deal with problems of the second type, and Chapters VI and VII deal with problems of the third and fourth type respectively. A few numerical problems have been included in each of these Chapters to demonstrate the efficiency of the algorithms involved. The class of optimal control problems considered in Chapter II consists of a nonlinear system, a nonlinear cost functional, initial equality constraints, and terminal equality constraints. A Sequential Gradient-Restoration Algorithm is used to devise an iterative algorithm for solving this class of problems. 'I'he convergence properties of the algorithm are investigated. The class of optimal control problems considered in Chapter III consists of a nonlinear system, a nonlinear cost functional, and terminal as well as interior points equality constraints. The technique of control parameterization and Liapunov concepts are used to solve this class of problems, A computational algorithm for solving a class of optimal control problems involving terminal and continuous state constraints or inequality type was developed by Rei. 103 in 1989. In Chapter IV, we extend the results of Ref. 103 to a more general class of constrained time-delayed optimal control problems, which involves terminal state equality constraints, as well as terminal state inequality constraints and continuous state inequality constraints. In Ref. 104, a computational scheme using the technique of control parameterization was developed for solving a class of optimal control problems in which the cost functional includes the full variation of control. Chapter V is a straightforward extension of Ref. 104 to the time-delayed case. However the main contribution of this chapter is that many numerical examples have been solved. In Chapter VI, a class of linear systems subject to sudden jumps in parameter values is considered. To solve this class of stochastic control problem, we try to seek for the best feedback control law depending only on the measurable output. Based on this idea, we convert the original problem into an approximate constrained deterministic optimization problem, which can be easily solved by any existing nonlinear programming technique. In Chapter VII, a chemical reactor problem and its control to achieve a desired output temperature is considered. A finite element Galerkin method is used to convert the original distributed optimal control problem into a quadratic programming problem with linear constraints, which can he solved by any standard quadratic programming software . / Andrew Chakane 2018

Quantum computers and quantum computing is a reality of the near feature. Companies such as Google and IBM have already declared they have built a quantum computer and tend to increase their size and capacity moving forward. Quantum computers have the ability to be exponentially more powerful than classical computers today. With this power modeling behavior of atoms or chemical reactions in unusual conditions, improving weather forecasts and traffic conditions become possible. Also, their ability to exponentially speed up some computations makes the security of todays data and items a major concern and interest. In the area of cryptography, some encryption schemes (such as RSA) are already deemed broken by the onset of quantum computing. Some encryption algorithms have already been created to be quantum secure and still more are being created each day. While these algorithms in use today are considered quantum-safe not much is known of what a quantum attack would look like on these algorithms. Specifically, this paper discusses how many quantum bits, quantum gates and even the depth of these gates that would be needed for such an attack. The research below was completed to shed light on these areas and offer some concrete numbers of such an attack. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2018. / FAU Electronic Theses and Dissertations Collection

Previous perspective reparameterizations approximate the aliasing errors for the points in a 2D space---the points along the view direction (i.e. horizontal plane in view space), from a geometric intuition. There's no explicit way to qualitatively analyze the aliasing elsewhere. We thus derive the global representation of aliasing functions based on the solid mathematical analysis. Using the global representation, we propose the Direction-adaptive Perspective Shadow Maps (DirPSMs) to offer enhanced shadow rendering in real-time applications. / Shadows are essential for the realism of computer-generated images, which dramatically enhance our perception of virtual scenes by providing useful visual hints. Even tremendous advances in graphics rendering algorithms and programmable GPUs have made real-time and photo-realistic rendering a reality, the synthesis of realistic shadowing effects is still challenging and computationally intensive. Shadow mapping is one of the most popular algorithms for real-time shadow rendering, which has been extensively adopted in real-time applications by its generality and efficiency. However, shadow mapping suffers from the inherent aliasing problems such as jagged shadow boundaries and incorrect self-shadowing due to the image-based nature. In this thesis, we present several shadow rendering techniques to render anti-aliased shadows via shadow mapping especially for large-scale and dynamic scenes. / The Parallel-Split Shadow Maps (PSSMs) scheme is first proposed for realistic and real-time shadow rendering towards next generation of three-dimensional computer games. This scheme splits the view frustum into multiple parts using clip planes parallel to the view plane, and then generates multiple smaller shadow maps for the split parts. A fast and robust split strategy based on the analysis of shadow map aliasing is developed, to produce a moderate aliasing distribution over the whole depth range. Hardware-specific accelerations are also implemented and tested to remove the extra rendering passes caused by using multiple shadow maps. / These techniques are intuitive to implement without using complex data structures. They are designed to improve both quality and performance of shadow rendering in large-scale and dynamic scenes. / With the observation that the sampling density at the light in the post-perspective space better accommodates the requirements for the reconstruction of shadowed images, perspective reparameterization techniques warp shadow maps using the perspective transform to reduce aliasing errors for the objects near the viewer. One limitation in this line of research is that the approximated representation of aliasing errors is only valid for the ideal case in which the light and view directions are orthogonal. We thus establish the generalized perspective reparameterization functions to adaptively adjust the warping strength as the light and/or viewer moves. With the direction-dependent representations of aliasing errors, we subsequently develop three enhanced perspective reparameterizations to better handle general cases, including Generalized Linear Perspective Reparameterization (GLPR), Generalized Minimum-Norm Perspective Reparameterization (GMNPR) and Focus-preserving Trapezoidal Shadow Maps (FTSMs). / Zhang, Fan. / "August 2007." / Adviser: Hanqiu Sun. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1126. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 147-155). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

Acquiring 3-D motion of a camera from image sequences is one of the key components in a wide range of applications such as human computer interaction. Given the 3-D structure, the problem of camera motion recovery can he solved using the model-based approaches, which are well-known and have good performance under a controlled environment. If prior information on the scene is not available, traditional Structure from Motion (SFM) algorithms, which simultaneously estimate the scene structure and pose information, are required. The research presented in this thesis belongs to a different category: Motion from Motion (MFM), in which the main concern is the camera position and orientation. To be more precise, MFM algorithms have the capability of estimating 3-D camera motion directly from 2-D image motion without the explicit reconstruction of the scene structure, even though the 3-D model structure is not known in prior. As keeping track of the structural information is no longer required, putting these types of algorithms into real applications is relatively easy and convenient. / It is demonstrated in the experiments that the proposed algorithms are efficient, stable and accurate compared to several existing approaches. Furthermore, they have been put into applications such as mixed reality, virtual reality, robotics and super-resolution to show their performance in real situations. / The objective of this thesis is to develop a high-speed recursive approach that tackles the MFM problem. On the way to the final goal, a series of methods, each having its own strengths and characteristics, have been studied. (1) The first algorithm computes the camera pose from a monocular image sequence. The trifocal tensor is incorporated into the Extended Kalman Filter (EKF) formulation. The step of computing the 3-D models can thus be eliminated. (2) The proposed approach is then extended to the recovery of motion from a stereo image sequence. By applying the trifocal tensor to a stereo vision framework, the trifocal constraint becomes more robust and is not likely to be degenerate. In addition, the twist motion model is adopted to parameterize the 3-D motion. It does not suffer from singularities as Euler angles, and is minimal as opposed to quaternion and the direct use of rotation matrix. (3) The third method introduces the Interacting Multiple Model Probabilistic Data Association Filter (IMMPDAF) to the MFM problem. The Interacting Multiple Model (IMM) technique allows the existence of more than one dynamic system and in return leads to improved accuracy and stability even under abrupt motion changes. The Probabilistic Data Association (PDA) framework makes the automatic selection of measurement sets possible, resulting in enhanced robustness to occlusions and moving objects. As the PDA associates stereo correspondences probabilistically, the explicit establishment of stereo matches is not necessary except during initialization, and the point features present in the outer region of the stereo images can be utilized. / Yu, Ying Kin. / "July 2007." / Adviser: Wong Kin Hong. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1125. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 120-130). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

Tsz-Shing Tam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 84-87). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Literature Review --- p.6 / Chapter 3 --- System Model --- p.12 / Chapter 3.1 --- Static Architecture --- p.12 / Chapter 3.2 --- Dynamics --- p.15 / Chapter 3.3 --- Communication Paradigm --- p.16 / Chapter 3.4 --- Metric --- p.17 / Chapter 4 --- Routing Algorithms --- p.19 / Chapter 4.1 --- Minimum Hops Algorithm (MHA) --- p.20 / Chapter 4.2 --- Minimum Cost Algorithm (MCA) --- p.21 / Chapter 4.3 --- Mesh Algorithm (MA) --- p.24 / Chapter 4.3.1 --- Construction of the Set of Min-hop Paths --- p.24 / Chapter 4.3.2 --- Choosing a Path in S0 --- p.29 / Chapter 4.4 --- k-mesh Algorithm (KMA) --- p.29 / Chapter 4.4.1 --- Finding Sk --- p.30 / Chapter 4.4.2 --- Choosing a path in Sk --- p.34 / Chapter 4.5 --- Revised Mesh Algorithm (RMA) --- p.34 / Chapter 5 --- Reservation Strategies --- p.36 / Chapter 5.1 --- Introduction --- p.36 / Chapter 5.2 --- Notations --- p.38 / Chapter 5.3 --- Basic Reservation Strategy (BRS) --- p.39 / Chapter 5.4 --- Enhanced Reservation Strategy (ERS) --- p.41 / Chapter 5.5 --- Successor Reservation Strategy (SRS) --- p.43 / Chapter 6 --- Experiment --- p.45 / Chapter 6.1 --- Comparison on Routing Algorithms --- p.47 / Chapter 6.2 --- Comparison on Reservation Strategies --- p.64 / Chapter 7 --- Conclusion --- p.72 / Chapter A --- Existence of paths in Sk --- p.75 / Chapter B --- Estimation of basic reservation strategy guaranteed time --- p.79 / Chapter B.1 --- Basic reservation strategy --- p.79 / Chapter B.2 --- Estimation on Guaranteed Duration --- p.80 / Bibliography --- p.83

Kwok-Shing Ho. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 69-71). / Abstracts in English and Chinese. / List of Figures --- p.vi / List of Tables --- p.vii / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Thesis Objectives --- p.6 / Chapter 1.3 --- Outline of Thesis --- p.8 / Chapter Chapter 2 --- The Spare Capacity Planning Problem --- p.9 / Chapter 2.1 --- Mathematical Model of the Spare Capacity Planning Problem --- p.12 / Chapter 2.1.1 --- Variable Definitions --- p.12 / Chapter 2.1.2 --- Objective Function and Constraints --- p.15 / Chapter 2.1.3 --- Complexity --- p.17 / Chapter 2.2 --- Greedy Algorithm - Spare Capacity Allocation and Planning Estimator (SCAPE) --- p.19 / Chapter 2.2.1 --- Working Principle of SCAPE --- p.20 / Chapter 2.2.2 --- Implementation of SCAPE --- p.22 / Chapter 2.2.3 --- Improved SCAPE --- p.23 / Chapter 2.3 --- Experimental Results and Discussion --- p.27 / Chapter 2.3.1 --- Experimental Platform --- p.27 / Chapter 2.3.2 --- Experiment about Accuracy of SCAPE --- p.27 / Chapter 2.3.3 --- Experiment about Minimization of Network Spare Capacity --- p.30 / Chapter 2.3.4 --- Experiment about Minimization of Network Spare Cost --- p.35 / Chapter 2.4 --- Conclusions --- p.38 / Chapter Chapter 3 --- Survivable All-Optical Network Design Problem --- p.39 / Chapter 3.1 --- Mathematical Model of the Survivable Network Design Problem --- p.42 / Chapter 3.2 --- Optimization Algorithms for Survivable Network Design Problem --- p.44 / Chapter 3.2.1 --- Modified Drop Algorithm (MDA) --- p.45 / Chapter 3.2.1.1 --- Drop Algorithm Introduction --- p.45 / Chapter 3.2.1.2 --- Network Design with MDA --- p.45 / Chapter 3.2.2 --- Genetic Algorithm --- p.47 / Chapter 3.2.2.1 --- Genetic Algorithm Introduction --- p.47 / Chapter 3.2.2.2 --- Network Design with GA --- p.48 / Chapter 3.2.3 --- Complexity of MDA and GA --- p.51 / Chapter 3.3 --- Experimental Results and Discussion --- p.52 / Chapter 3.3.1 --- Experimental Platform --- p.52 / Chapter 3.3.2 --- Experiment about Accuracy of MDA and GA --- p.52 / Chapter 3.3.3 --- Experiment about Principle of Survivable Network Design --- p.55 / Chapter 3.3.4 --- Experiment about Performance of MDA and GA --- p.58 / Chapter 3.4 --- Conclusions --- p.62 / Chapter Chapter 4 --- Conclusions and Future Work --- p.63 / Appendix A The Interference Heuristic for the path restoration scheme --- p.66 / Bibliography --- p.69 / Publications --- p.72

by Lam Cheung Fai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 174-179). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem Definition --- p.2 / Chapter 1.2 --- Motivation --- p.5 / Chapter 1.3 --- Problems --- p.7 / Chapter 1.3.1 --- Illumination Changes and Motions in Videos --- p.7 / Chapter 1.3.2 --- Variations in Video Scene Characteristics --- p.8 / Chapter 1.3.3 --- High Complexity of Algorithms --- p.10 / Chapter 1.3.4 --- Heterogeneous Approaches to Video Segmentation --- p.10 / Chapter 1.4 --- Objectives and Approaches --- p.11 / Chapter 1.5 --- Organization of the Thesis --- p.13 / Chapter 2 --- Related Work --- p.15 / Chapter 2.1 --- Algorithms for Uncompressed Videos --- p.16 / Chapter 2.1.1 --- Pixel-based Method --- p.16 / Chapter 2.1.2 --- Histogram-based Method --- p.17 / Chapter 2.1.3 --- Motion-based Algorithms --- p.18 / Chapter 2.1.4 --- Color-ratio Based Algorithms --- p.18 / Chapter 2.2 --- Algorithms for Compressed Videos --- p.19 / Chapter 2.2.1 --- Algorithms based on JPEG Image Sequences --- p.19 / Chapter 2.2.2 --- Algorithms based on MPEG Videos --- p.20 / Chapter 2.2.3 --- Algorithms based on VQ Compressed Videos --- p.21 / Chapter 2.3 --- Frame Difference Analysis Methods --- p.21 / Chapter 2.3.1 --- Scene Cut Detection --- p.21 / Chapter 2.3.2 --- Gradual Transition Detection --- p.22 / Chapter 2.4 --- Speedup Techniques --- p.23 / Chapter 2.5 --- Other Approaches --- p.24 / Chapter 3 --- Analysis and Enhancement of Existing Algorithms --- p.25 / Chapter 3.1 --- Introduction --- p.25 / Chapter 3.2 --- Video Segmentation Algorithms --- p.26 / Chapter 3.2.1 --- Frame Difference Metrics --- p.26 / Chapter 3.2.2 --- Frame Difference Analysis Methods --- p.29 / Chapter 3.3 --- Analysis of Feature Extraction Algorithms --- p.30 / Chapter 3.3.1 --- Pair-wise pixel comparison --- p.30 / Chapter 3.3.2 --- Color histogram comparison --- p.34 / Chapter 3.3.3 --- Pair-wise block-based comparison of DCT coefficients --- p.38 / Chapter 3.3.4 --- Pair-wise pixel comparison of DC-images --- p.42 / Chapter 3.4 --- Analysis of Scene Change Detection Methods --- p.45 / Chapter 3.4.1 --- Global Threshold Method --- p.45 / Chapter 3.4.2 --- Sliding Window Method --- p.46 / Chapter 3.5 --- Enhancements and Modifications --- p.47 / Chapter 3.5.1 --- Histogram Equalization --- p.49 / Chapter 3.5.2 --- DD Method --- p.52 / Chapter 3.5.3 --- LA Method --- p.56 / Chapter 3.5.4 --- Modification for pair-wise pixel comparison --- p.57 / Chapter 3.5.5 --- Modification for pair-wise DCT block comparison --- p.61 / Chapter 3.6 --- Conclusion --- p.69 / Chapter 4 --- Color Difference Histogram --- p.72 / Chapter 4.1 --- Introduction --- p.72 / Chapter 4.2 --- Color Difference Histogram --- p.73 / Chapter 4.2.1 --- Definition of Color Difference Histogram --- p.73 / Chapter 4.2.2 --- Sparse Distribution of CDH --- p.76 / Chapter 4.2.3 --- Resolution of CDH --- p.77 / Chapter 4.2.4 --- CDH-based Inter-frame Similarity Measure --- p.77 / Chapter 4.2.5 --- Computational Cost and Discriminating Power --- p.80 / Chapter 4.2.6 --- Suitability in Scene Change Detection --- p.83 / Chapter 4.3 --- Insensitivity to Illumination Changes --- p.89 / Chapter 4.3.1 --- Sensitivity of CDH --- p.90 / Chapter 4.3.2 --- Comparison with other feature extraction algorithms --- p.93 / Chapter 4.4 --- Orientation and Motion Invariant --- p.96 / Chapter 4.4.1 --- Camera Movements --- p.97 / Chapter 4.4.2 --- Object Motion --- p.100 / Chapter 4.4.3 --- Comparison with other feature extraction algorithms --- p.100 / Chapter 4.5 --- Performance of Scene Cut Detection --- p.102 / Chapter 4.6 --- Time Complexity Comparison --- p.105 / Chapter 4.7 --- Extension to DCT-compressed Images --- p.106 / Chapter 4.7.1 --- Performance of scene cut detection --- p.108 / Chapter 4.8 --- Conclusion --- p.109 / Chapter 5 --- Scene Change Detection --- p.111 / Chapter 5.1 --- Introduction --- p.111 / Chapter 5.2 --- Previous Approaches --- p.112 / Chapter 5.2.1 --- Scene Cut Detection --- p.112 / Chapter 5.2.2 --- Gradual Transition Detection --- p.115 / Chapter 5.3 --- DD Method --- p.116 / Chapter 5.3.1 --- Detecting Scene Cuts --- p.117 / Chapter 5.3.2 --- Detecting 1-frame Transitions --- p.121 / Chapter 5.3.3 --- Detecting Gradual Transitions --- p.129 / Chapter 5.4 --- Local Thresholding --- p.131 / Chapter 5.5 --- Experimental Results --- p.134 / Chapter 5.5.1 --- Performance of CDH+DD and CDH+DL --- p.135 / Chapter 5.5.2 --- Performance of DD on other features --- p.144 / Chapter 5.6 --- Conclusion --- p.150 / Chapter 6 --- Motion Vector Based Approach --- p.151 / Chapter 6.1 --- Introduction --- p.151 / Chapter 6.2 --- Previous Approaches --- p.152 / Chapter 6.3 --- MPEG-I Video Stream Format --- p.153 / Chapter 6.4 --- Derivation of Frame Differences from Motion Vector Counts --- p.156 / Chapter 6.4.1 --- Types of Frame Pairs --- p.156 / Chapter 6.4.2 --- Conditions for Scene Changes --- p.157 / Chapter 6.4.3 --- Frame Difference Measure --- p.159 / Chapter 6.5 --- Experiment --- p.160 / Chapter 6.5.1 --- Performance of MV --- p.161 / Chapter 6.5.2 --- Performance Enhancement --- p.162 / Chapter 6.5.3 --- Limitations --- p.163 / Chapter 6.6 --- Conclusion --- p.164 / Chapter 7 --- Conclusion and Future Work --- p.165 / Chapter 7.1 --- Contributions --- p.165 / Chapter 7.2 --- Future Work --- p.169 / Chapter 7.3 --- Conclusion --- p.171 / Bibliography --- p.174 / Chapter A --- Sample Videos --- p.180 / Chapter B --- List of Abbreviations --- p.183

by Vincent Wing-Shing Tse. / Thesis submitted in: December 1997. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 62-[64]). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Principles of Multirate Circuit Switching in Quantized Clos Network --- p.10 / Chapter 2.1 --- Formulation of Multirate Circuit Switching --- p.11 / Chapter 2.2 --- Call Level Routing in Quantized Clos Network --- p.12 / Chapter 2.3 --- Cell Level Routing in Quantized Clos Network --- p.16 / Chapter 2.3.1 --- Traffic Behavior in ATM Network --- p.17 / Chapter 2.3.2 --- Time Division Multiplexing in Multirate Circuit Switching and Cell-level Switching in ATM Network --- p.19 / Chapter 2.3.3 --- Cell Transmission Scheduling --- p.20 / Chapter 2.3.4 --- Capacity Allocation and Route Assignment at Cell-level --- p.29 / Chapter 3 --- Performance Evaluation of Different Implementation Schemes --- p.31 / Chapter 3.1 --- Global Control and Distributed Switching --- p.32 / Chapter 3.2 --- Implementation Schemes of Quantized Clos Network --- p.33 / Chapter 3.2.1 --- Classification of Switch Modules --- p.33 / Chapter 3.2.2 --- Bufferless Switch Modules Construction Scheme --- p.38 / Chapter 3.2.3 --- Buffered Switch Modules Construction Scheme --- p.42 / Chapter 3.3 --- Complexity Comparison --- p.44 / Chapter 3.4 --- Delay Performance of The Two Implementation Schemes --- p.47 / Chapter 3.4.1 --- Assumption --- p.47 / Chapter 3.4.2 --- Simulation Result --- p.50 / Chapter 4 --- Conclusions --- p.59 / Bibliography --- p.62

by Hui Chi Chun Ronald. / Thesis submitted in: December 1998. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 62-66). / Abstract also in Chinese. / Chapter Chapter 1. --- Introduction --- p.1 / Chapter Chapter 2. --- AON Architecture --- p.7 / Chapter 2.1 --- WCC Dimension Reduction Node Architecture --- p.10 / Chapter 2.2 --- Restoration of a Survivable AON --- p.13 / Chapter Chapter 3. --- Network Dimensioning Problem --- p.15 / Chapter 3.1 --- Problem Setting --- p.16 / Chapter 3.2 --- Two Solution Approaches --- p.16 / Chapter 3.2.1 --- Minimum Variance Algorithm (MVA) --- p.17 / Chapter 3.2.2 --- Minimum Variance Subroutine (MVS) --- p.19 / Chapter 3.3 --- Shortest Path Algorithm (SPA) --- p.21 / Chapter 3.4 --- An Illustrative Example --- p.22 / Chapter 3.5 --- Performance Comparisons --- p.26 / Chapter Chapter 4. --- Network Management for AON Restoration --- p.31 / Chapter 4.1 --- Surveillance Network --- p.31 / Chapter 4.2 --- Signaling Network --- p.32 / Chapter 4.3 --- Network Management System --- p.32 / Chapter 4.4 --- CCS7 Adaptation for Supporting AON Restoration --- p.34 / Chapter Chapter 5. --- Complete Restoration Algorithm for AON --- p.40 / Chapter 5.1 --- Link-Based Restoration Algorithm --- p.43 / Chapter 5.2 --- Source-Based Restoration Algorithm --- p.44 / Chapter 5.3 --- Case Studies --- p.45 / Chapter 5.3.1 --- Case I and II --- p.45 / Chapter 5.3.2 --- Case III --- p.50 / Chapter 5.4 --- Completely Restorable Network planning --- p.52 / Chapter 5.5 --- A Summary on Problem Formulations --- p.55 / Chapter Chapter 6. --- Conclusion --- p.57 / Reference --- p.62

Many state-of-the-art results in natural language processing (NLP) are achieved with statistical models involving latent variables. Unfortunately, computational problems associated with such models (for instance, finding the optimal parameter values) are typically intractable, forcing practitioners to rely on heuristic methods without strong guarantees. While heuristics are often sufficient for empirical purposes, their de-emphasis on theoretical aspects has certain negative ramifications. First, it can impede the development of rigorous theoretical understanding which can generate new ideas and algorithms. Second, it can lead to black art solutions that are unreliable and difficult to reproduce. In this thesis, we argue that spectral methods---that is, methods that use singular value decomposition or other similar matrix or tensor factorization---can effectively remedy these negative ramifications. To this end, we develop spectral methods for two unsupervised language processing tasks. The first task is learning lexical representations from unannotated text (e.g., hierarchical clustering of a vocabulary). The second task is estimating parameters of latent-variable models used in NLP applications (e.g., for unsupervised part-of-speech tagging). We show that our spectral algorithms have the following advantages over previous methods: 1. The algorithms provide a new theoretical framework that is amenable to rigorous analysis. In particular, they are shown to be statistically consistent. 2. The algorithms are simple to implement, efficient, and scalable to large amounts of data. They also yield results that are competitive with the state-of-the-art.