liu.seSearch for publications in DiVA
Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Rank Reduction and Volume Minimization Approach to State-Space Subspace System Identification
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics, Scientific Computing. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-1542-2690
2006 (English)In: Signal Processing, ISSN 0165-1684, E-ISSN 1872-7557, Vol. 86, no 11, p. 3275-3285Article in journal (Refereed) Published
##### Abstract [en]

In this paper we consider the reduced rank regression problem

solved by maximum-likelihood-inspired state-space subspace system identification algorithms. We conclude that the determinant criterion is, due to potential rank-deficiencies, not general enough to handle all problem instances. The main part of the paper analyzes the structure of the reduced rank minimization problem and identifies signal properties in terms of geometrical concepts. A more general minimization criterion is considered, rank reduction followed by volume minimization. A numerically sound algorithm for minimizing this criterion is presented and validated on both simulated and experimental data.

##### Place, publisher, year, edition, pages
Elsevier, 2006. Vol. 86, no 11, p. 3275-3285
##### Keywords [en]
Reduced rank regression, System identification, General algorithm, Determinant minimization criterion, Rank reduction, Volume minimization
##### National Category
Mathematics Control Engineering
##### Identifiers
OAI: oai:DiVA.org:liu-13191DiVA, id: diva2:18007
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2017-12-13
##### In thesis
1. Algorithms in data mining using matrix and tensor methods
Open this publication in new window or tab >>Algorithms in data mining using matrix and tensor methods
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis we discuss algorithms for the reduced rank regression problem and algorithms for the computation of the best multilinear rank approximation of tensors.

The first two papers deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is

$\min_{\rank(X) = k} \det (B - X A)(B - X A)\tp,$

where $A$ and $B$ are given matrices and we want to find $X$ under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on $A$ and $B$ so that $(B - X A)(B - X A)\tp$ is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing a singular objective matrix.

Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third paper concerns with classification of handwritten digits in the context of tensors or multidimensional data arrays. Tensor and multilinear algebra is an area that attracts more and more attention because of the multidimensional structure of the collected data in various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98--99 \% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The resulting algorithm achieves 5\% in classification error with fairly low amount of computations.

The remaining two papers discuss computational methods for the best multilinear

rank approximation problem

$\min_{\cB} \| \cA - \cB\|$

where $\cA$ is a given tensor and we seek the best low multilinear rank approximation tensor $\cB$. This is a generalization of the best low rank matrix approximation problem. It is well known that for matrices the solution is given by truncating the singular values in the singular value decomposition (SVD) of the matrix. But for tensors in general the truncated HOSVD does not give an optimal approximation. For example, a third order tensor $\cB \in \RR^{I \x J \x K}$ with rank$(\cB) = (r_1,r_2,r_3)$ can be written as the product

$\cB = \tml{X,Y,Z}{\cC}, \qquad b_{ijk}=\sum_{\lambda,\mu,\nu} x_{i\lambda} y_{j\mu} z_{k\nu} c_{\lambda\mu\nu},$

where $\cC \in \RR^{r_1 \x r_2 \x r_3}$ and $X \in \RR^{I \times r_1}$, $Y \in \RR^{J \times r_2}$, and $Z \in \RR^{K \times r_3}$ are matrices of full column rank. Since it is no restriction to assume that $X$, $Y$, and $Z$ have orthonormal columns and due to these constraints, the approximation problem can be considered as a nonlinear optimization problem defined on a product of Grassmann manifolds. We introduce novel techniques for multilinear algebraic manipulations enabling means for theoretical analysis and algorithmic implementation. These techniques are used to solve the approximation problem using Newton and Quasi-Newton methods specifically adapted to operate on products of Grassmann manifolds. The presented algorithms are suited for small, large and sparse problems and, when applied on difficult problems, they clearly outperform alternating least squares methods, which are standard in the field.

##### Place, publisher, year, edition, pages
Matematiska institutionen, 2008. p. 29
##### Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1178
##### Keywords
Volume, Minimization criterion, Determinant, Rank deficient matrix, Reduced rank regression, System identification, Rank reduction, Volume minimization, General algorithm, Handwritten digit classification, Tensors, Higher order singular value decomposition, Tensor approximation, Least squares, Tucker model, Multilinear algebra, Notation, Contraction, Tensor matricization, Newton's method, Grassmann manifolds, Product manifolds, Quasi-Newton algorithms, BFGS and L-BFGS, Symmetric tensor approximation, Local/intrinsic coordinates, Global/embedded coordinates;
##### National Category
Computational Mathematics
##### Identifiers
urn:nbn:se:liu:diva-11597 (URN)978-91-7393-907-2 (ISBN)
##### Public defence
2008-05-27, Glashuset, B-huset, ing. 25, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
##### Supervisors
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2013-10-11
2. Algorithms in data mining: reduced rank regression and classification by tensor methods
Open this publication in new window or tab >>Algorithms in data mining: reduced rank regression and classification by tensor methods
2005 (English)Licentiate thesis, comprehensive summary (Other academic)
##### Abstract [en]

In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis, which consists of three appended manuscripts, we discuss algorithms for reduced rank regression and for classification in the context of tensor theory.

The first two manuscripts deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is

where A and B are given matrices and we want to find X under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on A and B so that (B - XA)(B - XA)T is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing singularity on the objective matrix.

Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third appended manuscript concerns with classification of hand written digits in the context of tensors or multidimensional data arrays. Tensor theory is also an area that attracts more and more attention because of the multidimensional structure of the collected data in a various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98%- 99% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The amount of computations is fairly low and the performance reasonably good, 5% in error rate.

##### Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1214
Mathematics
##### Identifiers
urn:nbn:se:liu:diva-30272 (URN)15789 (Local ID)91-85457-81-7 (ISBN)15789 (Archive number)15789 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-11-06

#### Open Access in DiVA

No full text in DiVA

Publisher's full text

#### Authority records BETA

Lindgren, DavidSavas, Berkant

#### Search in DiVA

##### By author/editor
Lindgren, DavidSavas, Berkant
##### By organisation
Automatic ControlThe Institute of TechnologyScientific Computing
##### In the same journal
Signal Processing
##### On the subject
MathematicsControl Engineering

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 887 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf