Abstracts and Full Texts

Last updated: 5 April 2019 at 16:00:14 CEST


Feed-forward neural networks: a geometrical perspective [.pdf (376 kB)]

Marco Budinich and Edoardo Milotti

(Journal of Physics A: Mathematical and General 24 (1991) pp. 881-888)

Abstract - The convex hull of any subset of vertices of an n-dimensional hypercube contains
no other vertex of the hypercube. This result permits the application of some theorems of
n-dimensional geometry to digital feed-forward neural networks. Also, the construction of
the convex hull is proposed as an alternative to more traditional learning algorithms. Some
preliminary simulation results are reported.


On linear separability of random subsets of hypercube vertices [.pdf (136 kB)]

Marco Budinich

(Journal of Physics A: Mathematical and General 24 (1991) pp. L211-L213)

Abstract - The classical Cover results on linear separability of points in R^d are a milestone
in neural network theory. Nevertheless they are not valid for digital input networks because
in this case the points are not in general position being vertices of a d-dimensional hypercube.
I show here that for large d all Cover findings can be extended to this case. It is also
shown that for n < O((d + 1)^(3/2)) the number of linear separations of n random hypercube
vertices tends to that of n points in general position.


Properties of feedforward neural networks [.pdf (408 kB)]

Marco Budinich and Edoardo Milotti

(Journal of Physics A: Mathematical and General 25 (1992) pp. 1903-1914)

Abstract - In his seminal paper Cover used geometrical arguments to compute the probability
of separating two sets of patterns with a perceptron. We extend these ideas to feedforward
networks with hidden layers. There are intrinsic limitations to the number of patterns that
a net of this kind can separate and we find quantitative bounds valid far any net with d
input and h hidden neurons.


Some notes on perceptron learning [.pdf (624 kB)]

Marco Budinich

(Journal of Physics A: Mathematical and General 26 (1993) pp. 4237-4247)

Abstract - We extend the geometrical approach to the Perceptron and show that, given n
examples, learning is of maximal difficulty when the number of inputs d is such that n = 5d.
We then present a new Perceptron algorithm that takes advantage of the peculiarities of
the cost function. In our tests it is more than two times faster that the standard algorithm.
More importantly it does not have fixed parameters, like the usual learning constant \eta, but
it adapts them to the cost function. We show that there exist an optimal choice for \beta, the
steepness of the transfer function. We present also a brief systematic study of the
parameters \eta and \beta of the standard Perceptron algorithm.


On the Ordering Conditions for Self-Organising Maps

Marco Budinich and John G. Taylor

(Neural Computation 7 #2 (March 1995), pp. 284-289)

Abstract - We present a geometrical interpretation of ordering in self-organizing
feature maps. This view provides simpler proofs of Kohonen ordering theorem and of
convergence to an ordered state in the one dimensional case. At the same time it
explains intuitively the origin of the problems in higher dimensional cases.
Furthermore it provides a geometrical view of the known characteristics of learning
in self-organising nets.


A Self-Organising Neural Network for the Travelling Salesman Problem that is Competitive with Simulated Annealing [.pdf (40 kB)]

Marco Budinich

(Neural Computation 8 #2 (February 1996), pp. 416-424)

Abstract - Unsupervised learning applied to an unstructured neural network can give approximate
solutions to the travelling salesman problem. For 50 cities in the plane this algorithm performs
like the elastic net of Durbin and Willshaw [Durbin 1987] and it improves when increasing the
number of cities to get better than simulated annealing for problems with more than 500 cities.
In all the tests this algorithm requires a fraction of the time taken by simulated annealing.


A Neural Network for the Travelling Salesman Problem with a Well Behaved Energy Function [.pdf (61 kB)]

Marco Budinich and Barbara Rosario

(Contributed paper to MANNA Conference, Oxford, July 3-7, 1995))

Abstract - We present and analyze a Self Organizing Feature Map (SOFM) for the
NP-complete problem of the travelling salesman (TSP): finding the shortest closed
path joining N cities. Since the SOFM has discrete input patterns (the cities of the
TSP) one can examine its dynamics analytically. We show that, with a particular
choice of the distance function for the net, the energy associated to the SOFM has its
absolute minimum at the shortest TSP path. Numerical simulations confirm that this
distance augments performances. It is curious that the distance function having this
property combines the distances of the neuron and of the weight spaces.


Sorting with Self-Organising Maps

Marco Budinich

(Neural Computation 7 #6 (November 1995), pp. 1188-1190)

Abstract - A self-organising feature map sorts n real numbers in O(n) time apparently
violating the O(n log n) bound. Detailed analysis shows that the net takes advantage
of the uniform distribution of the numbers and, in this case, sorting in O(n) is possible.
There are, however, an exponentially small fraction of pathological distributions
producing O(n^2) sorting time. It is interesting to observe that standard learning
produced a smart sorting algorithm.


Multiple Cueing of an Associative Net [.pdf (2.8 MB)]

Marco Budinich, Bruce Graham and David Willshaw

International Journal of Neural Systems, 6 (supplementary issue), (1995) pp. 171-174.

Neural Networks For NP-Complete Problems

Marco Budinich

(Invited talk at World Conference on Nonlinear Analysis WCNA 96, Athens (Greece), 23-27 July 1996)

Abstract - Combinatorial optimization is an active field of research in Neural Networks.
Since the first attempts to solve the travelling salesman problem with Hopfield nets
several progresses have been made. I will present some Neural Network approximate
solutions for NP-complete problems that have a sound mathematical foundation and
that, beside their theoretical interest, are also numerically encouraging.
These algorithms easily deal with problems with thousands of instances taking Neural
Network approaches out of the "toy-problem" era.


Adaptive Calibration of Imaging Array Detectors [.ps (390 kB) or .pdf (145 kB)]

Marco Budinich and Renato Frison

(Neural Computation 11 #6 (August 1999), pp. 1281-1296)

Abstract - In this paper we present two methods for non-uniformity correction
of imaging array detectors based on neural networks, both of them exploit image
properties to supply lack of calibrations while maximizing the entropy of the
output. The first method uses a self-organizing net that produces a linear
correction of the raw data with coefficients that adapt continuously. The
second method employs a kind of contrast equalization curve to match pixel
distributions. Our work originates from Silicon detectors but the treatment is
general enough to be applicable to many kinds of array detectors like those
used in Infrared imaging or in high energy physics.


The Maximum Clique Problem [.ps (467 kB), .dvi (233 kB) or .pdf]

I.M. Bomze, M. Budinich, P.M. Pardalos and M. Pelillo

(in: Handbook of Combinatorial Optimization (Supp. Vol. A), Ding-Zhu Du and Panos M. Pardalos Editors,
Kluwer Academic Publishers, October 1999, pp. 656)

Abstract - The maximum clique problem is a classical problem in combinatorial
optimization which finds important applications in different domains. In this
paper we try to give a survey of results concerning algorithms, complexity, and
applications of this problem, and also provide an updated bibliography. Of
course, we build upon precursory works with similar goals.


Annealed Replication: A New Heuristic for the Maximum Clique Problem [.dvi (109 kB) or .pdf (224 kB)]

I.M. Bomze, M. Budinich, M. Pelillo and C. Rossi

(Discrete Applied Mathematics 121 #1-3 (25 September 2002), pp. 27-49)

Abstract - In this paper, a new heuristic for approximating the maximum clique
problem is proposed, based on a detailed analysis of a class of continuous
optimization models which provide a complete characterization of solutions to
this NP-hard combinatorial problem. The idea is to alter a regularization
parameter iteratively in such a way that an iterative procedure with the updated
parameter value would avoid unwanted, inefficient local solutions, i.e., maximal
cliques which contain less than the maximum possible number of vertices. The
local search procedure is performed with the help of the replicator dynamics,
and the regularization parameter is chosen deliberately as to render dynamical
instability of the (formerly) stable solutions which we want to discard in order
to get an improvement. In this respect, the proposed procedure differs from
usual simulated annealing approaches. To demonstrate the validity of this
approach, we report on the performance applied to selected DIMACS benchmark graphs.


Bounds on the Maximum Clique of a Graph [.dvi (36 kB) or .pdf (120 kB)]

Marco Budinich

(Discrete Applied Mathematics 127 #3 (1 May 2003), pp. 535-543)

The paper reviews some of the existing exact bounds to the maximum clique of a graph
and successively presents a new upper and a new lower bound. The new upper bound is
n - rank(AC)/2, where AC is the adjacency matrix of the complementary graph, and derives
from a formulation of the maximum clique problem in complex space. The new lower bound
(see text for details) improves strictly the present best lower bound published by Wilf
in 1986.
Throughout the paper an eye is kept on the computational complexity of actually calculating
the bounds. At the end, the various bounds are compared on 700 random graphs.


A Spinorial Formulation of the Maximum Clique Problem of a Graph [full text: arXiv:math-ph/0603068]

Marco Budinich and Paolo Budinich

(Journal of Mathematical Physics 47 #4, 043502, April 2006)

We present a new formulation of the maximum clique problem of a graph in complex space.
We start observing that the adjacency matrix A of a graph can always be written in the
form A = B B where B is a complex, symmetric matrix formed by vectors of zero length
(null vectors) and the maximum clique problem can be transformed in a geometrical problem
for these vectors. This problem, in turn, is translated in spinorial language and we show
that each graph uniquely identifies a set of pure spinors, that is vectors of the
endomorphism space of Clifford algebras, and the maximum clique problem is formalized in
this setting so that, this much studied problem, may take advantage from recent
progresses of pure spinor geometry.


Laboratorio a Scuola [full text: .pdf (8.3 MB)]

Alessando Borgnolo, Marco Budinich and Massimo Vascotto

in: Frascati Physics Series - Italian Collection, Collana: Scienza Aperta Vol. I (2006) - ComunicareFisica2005, Atti I Convegno "Comunicare Fisica e altre Scienze", Frascati 24-27 Ottobre 2005, p. 441-446.
Delineiamo le attivita' sviluppate negli ultimi anni dal Corso di Laurea in Fisica dell'Universita'
di Trieste per l'orientamento dei ragazzi delle scuole secondarie. Ci concentriamo sull'impianto
generale e sugli obbiettivi che ci siamo proposti di ottenere con queste iniziative.


The Maximum Clique Problem in Spinorial Form [full text: .pdf (92 kB)]

Marco Budinich and Paolo Budinich

BPU6 - Sixth International Conference of the Balkan Physical Union, Istanbul, Turkey, 22-26 August 2006, AIP Conference Proceedings 899, April 2007, p. 355-356.
We present a formulation of the Maximum Clique problem of a graph as a geometrical problem
of null vectors in complex space. This problem is then translated in spinorial language.


On the Transfer Functions for Complex Neurons [full text: .pdf (232 kB)]

Marco Budinich

paper submitted to: ICANN 2007 - International Conference on Artificial Neural Networks, Porto, Portugal, 9 - 13 September 2007
Since some time the extension of neural networks to the complex field C has received considerable
attention for possible applications to phenomena in which the variables contain also phase
information. In this paper we focus the attention on the complex transfer function. In compliance
to Liouville's theorem, that forbids entire bounded analytic functions, a frequent choice has been
to separate real and imaginary part of the output of a neuron. We show that this choice
corresponds to throwing the baby with the water since these kind of complex neurons are identical
to 2 purely real ones thus losing any possible complex advantage. On the contrary we show that a
neuron with an analytic transfer function provides an output that is not approximable by 2 real
neurons, like in the previous case, thus indirectly proving the superior computing power of truly
complex neurons.


The 'Radon School Survey': measuring radioactivity at home

[full text: .pdf (229 kB)]

Marco Budinich and Massimo Vascotto

Science in School 14 (April 2010), pp. 54-57;

Comunicare Fisica Attraverso lo Sport (in Italian) [full text: .pdf (935 kB)]

Anna Gregorio, Marco Budinich and Mario Fabretto

contributed paper to: ComunicareFisica2007, II Convegno "Comunicare Fisica e altre Scienze", Trieste 1-6 Ottobre 2007.
Scopo dell'iniziativa Ź di far avvicinare i giovani alla scienza e in particolare alla Fisica
tramite il naturale connubio della fisica con lo sport. L'abbinamento "Fisica e Sport" Ź dettato
dalla consapelovezza che spesso trascuriamo il fatto che la Fisica Ź alla base di molte delle
attivitą comuni di ogni giorno. Lo sport Ź solo una delle applicazioni pratiche della fisica che
coinvolge tutta la popolazione.


On Computational Complexity of Clifford Algebra [full text: .pdf (124 kB)]

Marco Budinich

Journal of Mathematical Physics 50 #5, 053514, 18 May 2009 (also DOI: 10.1063/1.3133042, arXiv:0904.0417v1 [math-ph]).
After a brief discussion of the computational complexity of Clifford algebras, we present a new basis
or even Clifford algebra Cl(2 m) that simplifies greatly the actual calculations and, without
resorting to the conventional matrix isomorphism formulation, obtains the same complexity. In the
last part we apply these results to the Clifford algebra formulation of the NP-complete problem of
the maximum clique of a graph introduced in a previous paper.
[Full text courtesy of: Journal of Mathematical Physics. Copyright (2009) American Institute of Physics. This article may be downloaded for personal use only. Any other use requires prior permission of the author and the American Institute of Physics.]

The Extended Fock Basis of Clifford Algebra [full text: .pdf (164 kB)]

Marco Budinich

Advances in Applied Clifford Algebra 22 #2, (2012), pp. 283-296; (also: DOI:10.1007/s00006-011-0316-2, arXiv:1006.1616v2 [math-ph]);
We investigate the properties of the Extended Fock Basis (EFB) of Clifford algebras [1]
with which one can replace the traditional multivector expansion of Cl(g) with an
expansion in terms of simple (also: pure) spinors. We show that a Clifford algebra with 2m
generators is the direct sum of 2m spinor subspaces S characterized as being left
eigenvectors of \Gamma; furthermore we prove that the well known isomorphism between
simple spinors and totally null planes holds only within one of these spinor subspaces. We
also show a new symmetry between spinor and vector spaces: similarly to a vector space of
dimension 2m that contains totally null planes of maximal dimension m, also a spinor space
of dimension 2m contains "totally simple planes", sub-spaces made entirely of simple
spinors, of maximal dimension m.


Neural Relax [full text: .pdf (721 kB)]

Elisa Benedetti and Marco Budinich

Neural Computation 24 #11 (November 2012) pp. 3091-3110, Massachussets (U.S.A.); (also: DOI:10.1162/NECO_a_00359, arXiv:1107.5472v2 [math-ph]).
Abstract - We present an algorithm for data preprocessing of an associative memory inspired to an
electrostatic problem that turns out to have intimate relations with information maximization.


On Spinors and Null Vectors [full text: .pdf (233 kB)]

Marco Budinich

Journal of Physics A: Mathematical and Theoretical 47 #11 (March 2014) p. 115201; (also: doi:10.1088/1751-8113/47/11/115201, arXiv:1208.0881 [math-ph]).
Abstract - We investigate the relations between spinors and null vectors in Clifford
algebra of any dimension with particular emphasis on the conditions that a spinor must
satisfy to be simple (also: pure). In particular we prove: i) a new property for null
vectors: each of them bisects spinor space into two subspaces of equal size; ii) that
simple spinors form one-dimensional subspaces of spinor space; iii) a necessary and
sufficient condition for a spinor to be simple that generalizes a theorem of Cartan and
Chevalley which becomes a corollary of this result. We also show how to write down easily
the most general spinor with a given associated totally null plane.


On Spinors of Zero Nullity [full text: .pdf (217 kB)]

Marco Budinich

Advances in Applied Clifford Algebra 25 #4, (2015), pp. 771-786; (also: DOI:10.1007/s00006-015-0547-8, arXiv:1405.7239 [math-ph])
Abstract - We present a necessary and sufficient condition for a spinor $\omega$ to be
of nullity zero, i.e. such that for any null vector $v$, $v \omega \ne 0$. This dives deeply
in the subtle relations between a spinor $\omega$ and $\omega_c$, the (complex) conjugate
of $\omega$ belonging to the same spinor space.


On Spinors Transformations [full text: .pdf (188 kB)]

Marco Budinich

Journal of Mathematical Physics 57 #7, 071703, 2016 (also DOI: 10.1063/1.4959531, arXiv:1603.02181 [math-ph]);
Abstract - We begin showing that for even dimensional vector spaces $V$ all automorphisms of their
Clifford algebras are inner. So all orthogonal transformations of $V$ are restrictions to $V$ of
inner automorphisms of the algebra. Thus under orthogonal transformations $P$ and $T$ --- space and
time reversal --- all algebra elements, including vectors $v$ and spinors $\varphi$, transform as
$v \to x v x^{-1}$ and $\varphi \to x \varphi x^{-1}$ for some algebra element $x$. We show that
while under combined $PT$ spinor $\varphi \to x \varphi x^{-1}$ remain in its spinor space, under
$P$ or $T$ separately $\varphi$ goes to a \emph{different} spinor space and may have opposite
chirality. We conclude with a preliminary characterization of inner automorphisms with respect to
their property to change, or not, spinor spaces.


On Clifford Algebras and binary integers [full text: .pdf (492 kB)]

Marco Budinich

Advances in Applied Clifford Algebra 27 #2, (2017), pp. 1007-1017; (also: DOI:10.1007/s00006-016-0735-1, arXiv:1605.07062 [math-ph]);
Abstract - We show that the binary representation of the integers has a role to play in
many aspects of Clifford algebras.


The Boolean SATisfiability Problem in Clifford algebra [full text: .pdf (197 kB)]

Marco Budinich

Theoretical Computer Science 2019, (also: doi: 10.1016/j.tcs.2019.03.027, arXiv:1704.02942v3 [math-ph]);
Abstract - We present a formulation of the Boolean Satisfiability Problem in spinor language that
allows to give a necessary and sufficient condition for unsatisfiability. With this result we
outline an algorithm to test for unsatisfiability with possibly interesting theoretical properties.


The transformations of spinors [full text: .pdf (299 kB)]

Marco Budinich

Journal of Physics: Conference Series 845, 012031, 2017 (also doi: 10.1088/1742-6596/845/1/012031)
Abstract - We begin showing that for even dimensional vector spaces $V$ all automorphisms of their
Clifford algebras are inner. So all orthogonal transformations of $V$ are restrictions to $V$ of
inner automorphisms of the algebra. Thus under orthogonal transformations $P$ and $T$ --- space and
time reversal --- all algebra elements, including vectors $v$ and spinors $\varphi$, transform as
$v \to x v x^{-1}$ and $\varphi \to x \varphi x^{-1}$ for some algebra element $x$. We show that
while under combined $PT$ spinor $\varphi \to x \varphi x^{-1}$ remain in its spinor space, under
$P$ or $T$ separately $\varphi$ goes to a \emph{different} spinor space and may have opposite
chirality. We conclude with a preliminary characterization of inner automorphisms with respect to
their property to change, or not, spinor spaces.


Clifford algebra as a bridge between discrete and continuous worlds

Marco Budinich

Advances in Applied Clifford Algebra 28:67, DOI:10.1007/s00006-018-0884-5
Abstract - There are several topics of Clifford algebra where discrete and continuous worlds are
deeply intertwined, one for all the Cartan theorem that expresses continuous automorphisms by a
succession of reflections, but they thrive separately an do not fit in a comprehensive picture.
We will focus on some cases where Clifford algebra manifestly shows discrete features with the hope
that shedding light on some details may help a more complete scenario to come out of darkness.

In particular we will tackle two themes: the first is the ubiquitous role played by the base two
expansion of integers in Clifford algebra: for example the interplay between the signature of the
vector space and the 'spinorial chessboard' or the determination of row and column indices of the
isomorphic matrix algebra. The second theme is the contribution that could give the Abelian
subalgebra of the idempotents to the solution of the SATisfiability problem, the mother of all
combinatorial problems.


On complex representations of Clifford algebra

Marco Budinich

Advances in Applied Clifford Algebra 29:18 (2019); (also: doi: 10.1007/s00006-018-0930-3, arXiv:1805.03126 [math-ph])
Abstract - We show that complex representations of Clifford algebra can always be reduced either
to a real or to a quaternionic algebra depending on signature of complex space thus showing that
complex spinors are unavoidably either real Majorana spinors or quaternionic spinors. We use this
result to support (1,3) signature for Minkowski space.


The Boolean SATisfiability Problem in Clifford algebra

Marco Budinich

contributed paper to: XXIII National Conference on Statistical Physics and Complex Systems, Parma, June 20-22, 2018, arXiv:1904.02629 [math-ph]
Abstract - The Boolean SATisfiability Problem (SAT) is the archetypical combinatorial problem and
more than 20 years ago the problem was formulated in the language of statistical mechanics.
This brought both theoretical insights and competitive solution algorithms in some instances.

In this work we present a completely different SAT formulation in the language of spinors -
Clifford algebra - that yields a purely geometrical necessary and sufficient condition for
unsatisfiability. With this result we outline an algorithm to test for unsatisfiability with
possibly interesting theoretical properties.

In this form the problem has some similarity with the Onsager solution of the two dimensional Ising
model and we discuss possible interchanges.


The Boolean SATisfiability Problem and the orthogonal group O(n) [full text: .pdf (156 kB)]

Marco Budinich

arXiv:1904.02629 [math-ph]
Abstract - We explore the relations between the Boolean Satisfiability Problem with n literals
and the orthogonal group O(n) and show that all 2^n possible solutions lie in the compact and
disconnected real manifold of dimension n(n-1)/2 of this group.


For any problem do not hesitate to send me an e-mail --> marco.budinich_AT_ts.infn.it.

Back to: M. Budinich's home page or publications page