Published articles, conference papers, and other references

Email me if you are not able to access papers from the journal web pages.
Google scholar profile.

B. Savas and L. Eldén. Krylov-type methods for tensor computations~I. Linear Algebra and its Applications. Vol. 438, pp. 891-918, 2013. (doi:10.1016/j.laa.2011.12.007) [Abstract] [BibTeX] [PDF]

Abstract: Several Krylov-type procedures are introduced that generalize matrix Krylov methods for tensor computations. They are denoted minimal Krylov recursion, maximal Krylov recursion, and contracted tensor product Krylov recursion. It is proved that, for a given tensor A with multilinear rank-(p; q; r), the minimal Krylov recursion extracts the correct subspaces associated to the tensor in p+q+r number of tensor-vector-vector multiplications. An optimized minimal Krylov procedure is described that, for a given multilinear rank of an approximation, produces a better approximation than the standard minimal recursion. We further generalize the matrix Krylov decomposition to a tensor Krylov decomposition. The tensor Krylov methods are intended for the computation of low multilinear rank approximations of large and sparse tensors, but they are also useful for certain dense and structured tensors for computing their higher order singular value decompositions or obtaining starting points for the best low-rank computations of tensors. A set of numerical experiments, using real-world and synthetic data sets, illustrate some of the properties of the tensor Krylov methods.

BibTeX:

@article{savas13,
  author = {Savas, B. and Eldén, L.},
  title = {Krylov-type methods for tensor computations~I},
  journal = {Linear Algebra and its Applications},
  year = {2013},
  volume = {438},
  pages = {891--918},
  note = {Special Issue on Tensors and Multilinear Algebra},
  doi = {10.1016/j.laa.2011.12.007}
}

X. Sui, T.-H. Lee, J. J. Whang, B. Savas, S. Jain, K. Pingali and I. S. Dhillon. Parallel Clustered Low-Rank Approximation of Graphs and Its Application to Link Prediction. In Languages and Compilers for Parallel Computing. Vol. 7760, pp. 76-95, 2013. Springer Berlin Heidelberg. (doi:10.1007/978-3-642-37658-0_6) (URL) [BibTeX]

BibTeX:

@incollection{sui12b,
  author = {Sui, X. and Lee, T.-H. and Whang, J. J. and Savas, B. and Jain, S. and Pingali, K. and Dhillon, I. S.},
  editor = {Kasahara, Hironori and Kimura, Keiji},
  title = {Parallel Clustered Low-Rank Approximation of Graphs and Its Application to Link Prediction},
  booktitle = {Languages and Compilers for Parallel Computing},
  publisher = {Springer Berlin Heidelberg},
  year = {2013},
  volume = {7760},
  pages = {76--95},
  url = {http://dx.doi.org/10.1007/978-3-642-37658-0_6},
  doi = {10.1007/978-3-642-37658-0_6}
}

H. H. Song, B. Savas, T. W. Cho, V. Dave, Z. Lu, I. S. Dhillon, Y. Zhang and L. Qiu. Clustered embedding of massive social networks. In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems. pp. 331-342, 2012. (doi:10.1145/2254756.2254796) [BibTeX] [PDF]

BibTeX:

@inproceedings{song12,
  author = {Song, H. H. and Savas, B. and Cho, T. W. and Dave, V. and Lu, Z. and Dhillon, I. S. and Zhang, Y. and Qiu, L.},
  title = {Clustered embedding of massive social networks},
  booktitle = {Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems},
  year = {2012},
  pages = {331--342},
  doi = {10.1145/2254756.2254796}
}

H. H. Song, B. Savas, T. W. Cho, V. Dave, Z. Lu, I. S. Dhillon, Y. Zhang and L. Qiu. Clustered Embedding of Massive Social Networks. Technical report TR-12-06, Department of Computer Science, The University of Texas at Austin, 2012. [BibTeX] [PDF]

BibTeX:

@techreport{song12tr,
  author = {Song, H. H. and Savas, B. and Cho, T. W. and Dave, V. and Lu, Z. and Dhillon, I. S. and Zhang, Y. and Qiu, L.},
  title = {Clustered Embedding of Massive Social Networks},
  year = {2012},
  number = {TR--12--06},
  institution = {Department of Computer Science, The University of Texas at Austin}
}

L. Eldén and B. Savas. Perturbation theory and optimality conditions for the best multilinear rank approximation of a tensor. SIAM Journal on Matrix Analysis and Applications. Vol. 32, pp. 1422-1450, 2011. (doi:10.1137/110823298) [Abstract] [BibTeX] [PDF]

Abstract: The problem of computing the best rank-(p,q,r) approximation of a third order tensor is considered. First the problem is reformulated as a maximization problem on a product of three Grassmann manifolds. Then expressions for the gradient and the Hessian are derived in a local coordinate system at a stationary point, and conditions for a local maximum are given. A first order perturbation analysis is performed using the Grassmann manifold framework. The analysis is illustrated in a few examples, and it is shown that the perturbation theory for the singular value decomposition is a special case of the tensor theory.

BibTeX:

@article{elden11,
  author = {Eldén, L. and Savas, B.},
  title = {Perturbation theory and optimality conditions for the best multilinear rank approximation of a tensor},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  year = {2011},
  volume = {32},
  pages = {1422--1450},
  doi = {10.1137/110823298}
}

B. Savas and I. S. Dhillon. Clustered low rank approximation of graphs in information science applications. In Proceedings of the SIAM International Conference on Data Mining (SDM). pp. 164-175, 2011. (URL) [Abstract] [BibTeX] [PDF]

Abstract: In this paper we present a fast and accurate procedure called clustered low rank matrix approximation for massive graphs. The procedure involves a fast clustering of the graph and then approximates each cluster separately using existing methods, e.g. the singular value decomposition, or stochastic algorithms. The cluster-wise approximations are then extended to approximate the entire graph. This approach has several benets: (1) important community structure of the graph is preserved due to the clustering; (2) highly accurate low rank approximations are achieved; (3) the procedure is ecient both in terms of computational speed and memory usage; (4) better performance in problems from various applications compared to standard low rank approximation. Further, we generalize stochastic algorithms to the clustered low rank approximation framework and present theoretical bounds for the approximation error. Finally, a set of experiments, using large scale and real-world graphs, show that our methods outperform standard low rank matrix approximation algorithms.

BibTeX:

@inproceedings{savas11,
  author = {Savas, B. and Dhillon, I.~S.},
  title = {Clustered low rank approximation of graphs in information science applications},
  booktitle = {Proceedings of the SIAM International Conference on Data Mining (SDM)},
  year = {2011},
  pages = {164--175},
  note = {Single-blind review process. Acceptance rate: 82 of 344 submitted papers (23.84.},
  url = {http://siam.omnibooksonline.com/2011datamining/data/papers/080.pdf#page=1}
}

V. Vasuki, N. Natarajan, Z. Lu, B. Savas and I. S. Dhillon. Scalable Affiliation Recommendation using Auxiliary Networks. ACM Transactions on Intelligent Systems and Technology. Vol. 3, pp. 3:1-3:20, October 2011. (doi:10.1145/2036264.2036267) (URL) [Abstract] [BibTeX]

Abstract: Social network analysis has attracted increasing attention in recent years. In many social networks, besides friendship links among users, the phenomenon of users associating themselves with groups or communities is common. Thus, two networks exist simultaneously: the friendship network among users, and the affiliation network between users and groups. In this article, we tackle the affiliation recommendation problem, where the task is to predict or suggest new affiliations between users and communities, given the current state of the friendship and affiliation networks. More generally, affiliations need not be community affiliations---they can be a user?s taste, so affiliation recommendation algorithms have applications beyond community recommendation. In this article, we show that information from the friendship network can indeed be fruitfully exploited in making affiliation recommendations. Using a simple way of combining these networks, we suggest two models of user-community affinity for the purpose of making affiliation recommendations: one based on graph proximity, and another using latent factors to model users and communities. We explore the affiliation recommendation algorithms suggested by these models and evaluate these algorithms on two real-world networks, Orkut and Youtube. In doing so, we motivate and propose a way of evaluating recommenders, by measuring how good the top 50 recommendations are for the average user, and demonstrate the importance of choosing the right evaluation strategy. The algorithms suggested by the graph proximity model turn out to be the most effective. We also introduce scalable versions of these algorithms, and demonstrate their effectiveness. This use of link prediction techniques for the purpose of affiliation recommendation is, to our knowledge, novel.

BibTeX:

@article{vasuki11,
  author = {Vasuki, V. and Natarajan, N. and Lu, Z. and Savas, B. and Dhillon, I.~S.},
  title = {Scalable Affiliation Recommendation using Auxiliary Networks},
  journal = {ACM Transactions on Intelligent Systems and Technology},
  year = {2011},
  volume = {3},
  pages = {3:1--3:20},
  url = {http://doi.acm.org/10.1145/2036264.2036267},
  doi = {10.1145/2036264.2036267}
}

Z. Lu, B. Savas, W. Tang and I. S. Dhillon. Supervised link prediction using multiple sources. In Proceedings of the IEEE International Conference on Data Mining (ICDM). pp. 923-928, 2010. (doi:10.1109/ICDM.2010.112) [Abstract] [BibTeX]

Abstract: Link prediction is a fundamental problem in social network analysis and modern-day commercial applications such as Facebook and Myspace. Most existing research approaches this problem by exploring the topological structure of a social network using only one source of information. However, in many application domains, in addition to the social network of interest, there are a number of auxiliary social networks
and/or derived proximity networks available. The contribution of the paper is twofold: (1) a supervised learning framework that can effectively and efficiently learn the dynamics of social networks in the presence of auxiliary networks; (2) a feature design scheme for constructing a rich variety of path-based features using multiple sources, and an effective feature selection strategy based on structured sparsity. Extensive experiments on three real-world collaboration networks show that our model can effectively learn to predict new links using multiple sources, yielding higher prediction accuracy than unsupervised and singlesource supervised models.

BibTeX:

@inproceedings{lu10,
  author = {Lu, Z. and Savas, B. and Tang, W. and Dhillon, I. S.},
  title = {Supervised link prediction using multiple sources},
  booktitle = {Proceedings of the IEEE International Conference on Data Mining (ICDM)},
  year = {2010},
  pages = {923--928},
  note = {Double-blind review process. Acceptance rate: 155 of 793 submitted papers (19.55},
  doi = {10.1109/ICDM.2010.112}
}

Z. Lu, B. Savas, W. Tang and I. S. Dhillon. Supervised link prediction using multiple sources. Technical report TR-10-35, Department of Computer Science, The University of Texas at Austin, 2010. [BibTeX] [PDF]

BibTeX:

@techreport{lu10tr,
  author = {Lu, Z. and Savas, B. and Tang, W. and Dhillon, I. S.},
  title = {Supervised link prediction using multiple sources},
  year = {2010},
  number = {TR--10--35},
  institution = {Department of Computer Science, The University of Texas at Austin}
}

B. Savas and L.-H. Lim. Quasi-Newton Methods on Grassmannians and Multilinear Approximations of Tensors. SIAM Journal on Scientific Computing. Vol. 32, pp. 3352-3393, 2010. (doi:10.1137/090763172) [Abstract] [BibTeX] [PDF]

Abstract: In this paper we proposed quasi-Newton and limited memory quasi-Newton methods for objective functions defined on Grassmannians or a product of Grassmannians. Specifically we defined BFGS and limited memory BFGS updates in local and global coordinates on Grassmannians or a product of these. We proved that, when local coordinates are used, our BFGS updates on Grassmannians share the same optimality property as the usual BFGS updates on Euclidean spaces. When applied to the best multilinear rank approximation problem for general and symmetric tensors, our approach yields fast, robust, and accurate algorithms that exploit the special Grassmannian structure of the respective problems and which work on tensors of large dimensions and arbitrarily high order. Extensive numerical experiments are included to substantiate our claims.

BibTeX:

@article{savas10,
  author = {Savas, B. and Lim, L.-H.},
  title = {Quasi-Newton Methods on Grassmannians and Multilinear Approximations of Tensors},
  journal = {SIAM Journal on Scientific Computing},
  year = {2010},
  volume = {32},
  pages = {3352--3393},
  doi = {10.1137/090763172}
}

B. Savas and I. S. Dhillon. Fast and accurate low rank approximation of massive graphs. Technical report TR-10-18, Department of Computer Science, The University of Texas at Austin, 2010. [BibTeX] [PDF]

BibTeX:

@techreport{savas10c,
  author = {Savas, B. and Dhillon, I. S.},
  title = {Fast and accurate low rank approximation of massive graphs},
  year = {2010},
  number = {TR--10--18},
  institution = {Department of Computer Science, The University of Texas at Austin}
}

L. Eldén and B. Savas. A Newton--Grassmann Method for Computing the Best Multilinear Rank-($r_1,r_2,r_3$) Approximation of a Tensor. SIAM Journal on Matrix Analysis and Applications. Vol. 31, pp. 248-271, 2009. (doi:10.1137/070688316) [Abstract] [BibTeX] [PDF]

Abstract: We derive a Newton method for computing the best rank-$(r_1,r_2,r_3)$ approximation of a given $J x K x L$ tensor $$. The problem is formulated as an approximation problem on a product of Grassmann manifolds. Incorporating the manifold structure into Newton's method ensures that all iterates generated by the algorithm are points on the Grassmann manifolds. We also introduce a consistent notation for matricizing a tensor, for contracted tensor products and some tensor-algebraic manipulations, which simplify the derivation of the Newton equations and enable straightforward algorithmic implementation. Experiments show a quadratic convergence rate for the Newton-Grassmann algorithm.

BibTeX:

@article{elden09,
  author = {Eldén, L. and Savas, B.},
  title = {A Newton--Grassmann Method for Computing the Best Multilinear Rank-($r_1,r_2,r_3$) Approximation of a Tensor},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  year = {2009},
  volume = {31},
  pages = {248--271},
  doi = {10.1137/070688316}
}

B. Savas and L. Eldén. Krylov subspace methods for tensor computations. Technical report LITH-MAT-R-2009-02-SE, Department of Mathematics, Linköping University, 2009. [BibTeX] [PDF]

BibTeX:

@techreport{savas09,
  author = {Savas, B. and Eldén, L.},
  title = {Krylov subspace methods for tensor computations},
  year = {2009},
  number = {LITH-MAT-R--2009--02--SE},
  institution = {Department of Mathematics, Linköping University}
}

B. Savas. Algorithm Package Manual: Best Low Rank Tensor Approximation. Department of Mathematics, Link\"{o}ping Univeristy, 2008. (URL) [BibTeX] [PDF]

BibTeX:

@misc{savas08a,
  author = {Savas, B.},
  title = {Algorithm Package Manual: Best Low Rank Tensor Approximation},
  howpublished = {Department of Mathematics, Linköping Univeristy},
  year = {2008},
  url = {http://www.mai.liu.se/~besav/soft.html}
}

B. Savas. Toolbox for Grassmann Manifold Computations. Department of Mathematics, Link\"{o}ping Univeristy, 2008. (URL) [BibTeX] [PDF]

BibTeX:

@misc{savas08b,
  author = {Savas, B.},
  title = {Toolbox for Grassmann Manifold Computations},
  howpublished = {Department of Mathematics, Linköping Univeristy},
  year = {2008},
  url = {http://www.mai.liu.se/~besav/soft.html}
}

B. Savas. Algorithms in Data Mining using Matrix and Tensor Methods. Linköping Studies in Science and Technology, Dissertations, No 1178, Linköping University, Department of Mathematics 2008. (URL) [BibTeX]

BibTeX:

@phdthesis{savasphd,
  author = {Savas, B.},
  title = {Algorithms in Data Mining using Matrix and Tensor Methods},
  school = {Linköping University},
  year = {2008},
  url = {http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-11597}
}

B. Savas and L.-H. Lim. Best multilinear rank approximation of tensors with quasi-Newton methods on Grassmannians. Technical report LiTH-MAT-R-2008-01-SE, Department of Mathematics, Linköping University, April 2008. [BibTeX]

BibTeX:

@techreport{savlim08,
  author = {Savas, B. and Lim, L.-H.},
  title = {Best multilinear rank approximation of tensors with quasi-Newton methods on Grassmannians},
  year = {2008},
  number = {LiTH-MAT-R--2008--01--SE},
  institution = {Department of Mathematics, Linköping University}
}

L. Eldén and B. Savas. A Newton--Grassmann method for computing the Best Multi-Linear Rank-($r_1,r_2,r_3$) Approximation of a Tensors. Technical report LITH-MAT-R-2007-6-SE, Department of Mathematics, Linköping Universitet, 2007. [Abstract] [BibTeX]

BibTeX:

@techreport{elsa07,
  author = {Eldén, L. and Savas, B.},
  title = {A Newton--Grassmann method for computing the Best Multi-Linear Rank-($r_1,r_2,r_3$) Approximation of a Tensors},
  year = {2007},
  number = {LITH-MAT-R--2007--6--SE},
  institution = {Department of Mathematics, Linköping Universitet}
}

B. Savas and L. Eldén. Handwritten digit classification using higher order singular value decomposition. Pattern Recognition. Vol. 40, pp. 993-1003, 2007. (doi:10.1016/j.patcog.2006.08.004) [Abstract] [BibTeX]

Abstract: In this paper we present two algorithms for handwritten digit classification based on the higher order singular value decomposition (HOSVD). The first algorithm uses HOSVD for construction of the class models and achieves classification results with error rate lower than 6%. The second algorithm uses the HOSVD for tensor approximation simultaneously in two modes. Classification results for the second algorithm are almost down at 5% even though the approximation reduces the original training data with more than 98% before the construction of the class models. The actual classification in the test phase for both algorithms is conducted by solving a series least squares problems. Considering computational amount for the test presented the second algorithm is twice as efficient as the first one.

BibTeX:

@article{savas07,
  author = {Savas, B. and Eldén, L.},
  title = {Handwritten digit classification using higher order singular value decomposition},
  journal = {Pattern Recognition},
  year = {2007},
  volume = {40},
  pages = {993--1003},
  doi = {10.1016/j.patcog.2006.08.004}
}

B. Savas. Dimensionality reduction and volume minimization---generalization of the determinant minimization criterion for reduced rank regression problems. Linear Algebra and its Applications. Vol. 418, pp. 201-214, 2006. (doi:10.1016/j.laa.2006.01.032) [Abstract] [BibTeX]

Abstract: In this article we propose a generalization of the determinant minimization criterion. The problem of minimizing the determinant of a matrix expression has implicit assumptions that the objective matrix is always nonsingular. In case of singular objective matrix the determinant would be zero and the minimization problemwould be meaningless. To be able to handle all possible cases we generalize the determinant criterion to rank reduction and volume minimization of the objective matrix. The generalized minimization criterion is used to solve the following ordinary reduced rank regression problem:

min_X det(B - XA)(B - XA)^T, such that rank(X)=k,

where A and B are known and X is to be determined. This problem is often encountered in the system identification context.

BibTeX:

@article{savas06,
  author = {B. Savas},
  title = {Dimensionality reduction and volume minimization---generalization of the determinant minimization criterion for reduced rank regression problems},
  journal = {Linear Algebra and its Applications},
  year = {2006},
  volume = {418},
  pages = {201--214},
  doi = {10.1016/j.laa.2006.01.032}
}

B. Savas and D. Lindgren. Rank reduction and volume minimization approach to state-space subspace system identification. Signal processing. Vol. 86, pp. 3275-3285, 2006. (doi:10.1016/j.sigpro.2006.01.008) [Abstract] [BibTeX]

Abstract: In this paper we consider the reduced rank regression problem

min_L, L_3 det (Y_a - L P_b - L_3 U_a) (Y_a - L P_b - L_3 U_a)^T, such that rank(L) = n,

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.

BibTeX:

@article{savas06a,
  author = {Savas, B. and Lindgren, D.},
  title = {Rank reduction and volume minimization approach to state-space subspace system identification},
  journal = {Signal processing},
  year = {2006},
  volume = {86},
  pages = {3275--3285},
  doi = {10.1016/j.sigpro.2006.01.008}
}

L. Eldén and B. Savas. The maximum likelihood estimate in reduced-rank regression. Numerical Linear Algebra with Applications. Vol. 12, pp. 731-741, 2005. (doi:10.1002/nla.447) [Abstract] [BibTeX]

Abstract: In previous work by Stoica and Viberg the reduced-rank regression problem is solved in a maximum likelihood sense. The present paper proposes an alternative numerical procedure. The solution is written in terms of the principal angles between subspaces spanned by the data matrices. It is demonstrated that the solution is meaningful also in the case when the maximum likelihood criterion is not valid. A numerical example is given.

BibTeX:

@article{elden05,
  author = {Eldén, L. and Savas, B.},
  title = {The maximum likelihood estimate in reduced-rank regression},
  journal = {Numerical Linear Algebra with Applications},
  year = {2005},
  volume = {12},
  pages = {731--741},
  doi = {10.1002/nla.447}
}

B. Savas. Dimensionality Reduction and Volume Minimization---Generalization of the Determinant Minimization Criterion for Reduced Rank Regression Problems. Technical report LITH-MAT-R-2005-11-SE, Department of Mathematics, Linköping University, 2005. [BibTeX]

BibTeX:

@techreport{savas05,
  author = {B. Savas},
  title = {Dimensionality Reduction and Volume Minimization---Generalization of the Determinant Minimization Criterion for Reduced Rank Regression Problems},
  year = {2005},
  number = {LITH-MAT-R--2005--11--SE},
  institution = {Department of Mathematics, Linköping University}
}

B. Savas and D. Lindgren. Rank Reduction and Volume Minimization Algorithm for State-Space Subspace System Identification. Technical report LITH-MAT-R-2005-13-SE, Department of Mathematics, Linköping University, 2005. [BibTeX]

BibTeX:

@techreport{savas05b,
  author = {Savas, B. and Lindgren, D.},
  title = {Rank Reduction and Volume Minimization Algorithm for State-Space Subspace System Identification},
  year = {2005},
  number = {LITH-MAT-R--2005--13--SE},
  institution = {Department of Mathematics, Linköping University}
}

B. Savas and L. Eldén. Handwritten Digit Classification using Higher Order Singular Value Decompositions. Technical report LITH-MAT-R-2005-14-SE, Department of Mathematics, Linköping University, 2005. [BibTeX]

BibTeX:

@techreport{savas05c,
  author = {Savas, B. and Eldén, L.},
  title = {Handwritten Digit Classification using Higher Order Singular Value Decompositions},
  year = {2005},
  number = {LITH-MAT-R--2005--14--SE},
  institution = {Department of Mathematics, Linköping University}
}

B. Savas. Analyses and Tests of Handwritten Digit Recognition Algorithms. Master's Thesis LiTH-MAT-EX--2003--1, Department of Mathematics, Linköping University, 2003. [BibTeX] [PDF]

BibTeX:

@mastersthesis{savas03,
  author = {Savas, B.},
  title = {Analyses and Tests of Handwritten Digit Recognition Algorithms},
  school = {Department of Mathematics, Linköping University},
  year = {2003}
}

Sidansvarig: Berkant Savas
Senast uppdaterad: 2013-04-12

Linköpings Universitet

Berkant Savas, PhD

Published articles, conference papers, and other references