Parsimonious Least Norm Approximation.
A theoretically justifiable fast finite successive linear approximation algorithm is proposed for obtaining a parsimonious solutionto a corrupted linear system Ax=b+p, where the corruptionp is due to noise or error in measurement. The proposedlinear-programming-based algorithm finds a solutionx by parametrically minimizing the number of nonzeroelements in x and the error &Verbar;Ax-b-p&Verbar;_1.Numerical tests on a signal-processing-based exampleindicate that the proposed method is comparable to a method that parametrically minimizesthe1 -norm of the solution x and the error &Verbar;Ax-b-p&Verbar;_1, and that both methods are superior, byorders of magnitude, to solutions obtained by least squares as well by combinatorially choosing an optimal solution with a specific number of nonzero elements.
Introduction
A wide range of important applications can be reduced to the problem of estimating a vector x by
minimizing some norm of the residual vector Ax \Gamma b arising from a possibly inconsistent system of
linear equations:
where A is an m \Theta n real matrix and b is an m \Theta 1 vector, and both A and b are subject to
error. Methods for solving such problems include least squares [15], total least squares [11, 14] and
structured total least norm [24, 13].
In this paper we consider the closely related problem of minimizing the 1-norm of the residual
vector is subject to error and with the additional condition that only a specified
number of columns of A are used. This is clearly a combinatorial problem which is closely
related to the NP-hard problem considered by Amaldi and Kann [2] and consisting of solving a
consistent system of linear inequalities or equalities with rational entries such that the solution x has
a minimal number of nonzeros. We shall solve our problem by a novel method, based on minimizing
a concave function on a polyhedral set, that has been successfully used in such machine learning
problems as misclassification minimization [17], and feature selection [6] and in data mining [5, 19].
Mathematical Programming Technical Report 97-03, March 1997 - Revised September & November 1997. This
material is based on research supported by National Science Foundation Grants CCR-9322479 and CCR-9509085,
and Air Force Office of Scientific Research Grant AFOSR-144-GC92.
y Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, Madison, WI 53706,
paulb@cs.wisc.edu
z Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, Madison, WI 53706,
olvi@cs.wisc.edu. This author gratefully acknowledges the gracious hospitality of the Mathematics Department of
the University of California at San Diego during his sabbatical leave January-May 1997.
x Computer Science & Engineering, University of California San Diego, La Jolla, CA 92093 jbrosen@ucsd.edu
The idea behind using as few columns of A as possible to span b is motivated by the parsimony
principle of machine learning, known as Occam's Razor [26, 4], which says in essence: "simplest is
best". This principle is highly effective for generalization purposes [16, 25, 30] where, for example,
one wishes to use the "solution" x of (1) on new data not represented by the rows of [A b] as would
be the case if either A or b is corrupted by noise. The use of the 1-norm will enable us to use a
finite algorithm based on the polyhedral concave minimization approach which, as indicated above,
has been successfully used on difficult machine learning problems. In particular we will eventually
cast the problem as that of minimizing a concave function on a polyhedral set and begin with the
following unconstrained minimization problem:
min
Here e is a column vector of ones, the prime denotes the transpose, j \Delta j denotes the absolute value
function applied componentwise to a vector and (\Delta)   is the step function applied componentwise
also. The step function takes the value 0 if its argument is nonpositive, and the value 1 if its
argument is positive. The vector b will be corrupted by a noise vector p in our application. We
note immediately that when problem (2) is the classical least 1-norm approximation problem.
problem (2) is trivially solved by and is of no interest. We are interested in
solutions to problem (2) with - 2 [0; 1) that make e 0 jxj   - k for some desired k ! n and such that
acceptably small. In fact problem (2) can be viewed as a multiobjective optimization
problem [8] with the the two objectives of parsimony in the number of nonzero components of x
and smallness of the error kAx \Gamma bk 1 . By letting - range over the interval [0; 1] the cardinality of
the nonzero elements of the solution x varies from a maximum of n to 0, while the error kAx
will be nondecreasing monotonically. Depending on the problem, one of those x's will be the most
desirable. In many of the machine learning applications small values of - such as 0:05 often gave
parsimonious results that improved tenfold cross-validation [6]. We shall call problem (2), with a
possibly noise-corrupted b, the parsimonious least norm approximation problem (PLNA).
Our approach here for solving (2) will be to convert it to a concave minimization problem on
a polyhedral set (problem (12) below). We first show that this problem always has a solution
(Theorem 2.1 below). We then replace the discontinuous step function in the objective function of
below by an exponential smooth function in problem (14) below, just as was done in [18, 6],
and relate the two problems. Our novel theorem (Theorem 2.1 below) shows that the continuous
problem yields an exact solution of the discontinuous problem once a repeating optimal vertex
is identified for increasing but finite values of the smoothing parameter ff. We then prescribe a
linear-programming-based successive linearization algorithm SLA 3.1 for the solution of the smooth
problem and establish its finite termination in Theorem 3.2.
For comparative purposes we shall also employ Vapnik's support vector machine approach [29, 3]
of minimizing the size of the solution vector x as well as the error kAx decreasing
the VC dimension [29, p 76] (a capacity measure) and improving generalization. We shall do that
by parametrically minimizing the 1-norm of x as well as the 1-norm of the error Ax \Gamma b:
min
We shall call this problem, with a possibly noise-corrupted b, the least least norm approximation
problem and solve it by solving the equivalent linear programming formulation:
min
A word about our notation and background material. All vectors will be column vectors unless
transposed to a row vector by a prime superscript 0 . For a vector x in the n-dimensional real space
R n , jxj will denote a vector of absolute values of components x of x. The scalar
product of two vectors x and y in the n-dimensional real space will be denoted by x 0 y. For a linear
program min
c 0 x, the notation arg vertex min
c 0 x will denote the set of vertex solutions of the linear
program. For x 2 R n ; the norm kxk 2 will denote the 2-norm:
will denote the
1-norm:
For an m \Theta n matrix A; A i will denote the ith row of A and A ij will denote the
element in row i and column j. The identity matrix in a real space of arbitrary dimension will be
denoted by I ; while a column vector of ones of arbitrary dimension will be denoted by e. The base
of the natural logarithm will be denoted by ", and for y \Gammay will denote a vector in R m with
component " \Gammay m. For a function f : R n ! R that is concave on R n , the supergradient
@f(x) of f at x is a vector in R n satisfying
for any y 2 R n . The set D(f(x)) of supergradients of f at the point x is nonempty, convex, compact
and reduces to the ordinary gradient rf(x), when f is differentiable at x [22, 23]. For a vector
will denote the cardinality of the nonzero elements of x.
2 The Concave Minimization Problem
In this section we shall consider the minimization problem
min
where f is a concave function on R k which is bounded below on S, - is a nonnegative real number,
h is a nonnegative vector in R k and S is a polyhedral set in R k not containing straight lines that
go to infinity in both directions. Note that if the objective function of (6) is concave (which it
is not in general because of the nonconcavity of h 0 jsj   ) then by [23, Corollary 32.3.3] problem (6)
has a solution and by [23, Corollary 32.3.4] it has a vertex solution since S contains no straight
lines that go to infinity in both directions. However despite this lack of concavity we shall show
precisely the existence of a vertex solution by a novel approach which approximates the step function
on the nonnegative real line from below by an exponential. This smooth approximation will
also serve as a means for generating a finitely terminating algorithm at a stationary point of (6).
Another important feature is that an exact solution of (6) is obtained from a solution of the smooth
approximation for a finite value of the smoothing parameter.
We state now our smooth approximation of (6) as follows
min
where ff is a positive number. We have the obvious relation
Hence the smooth problem (7) minimum provides an underestimate to the minimum of problem
(6). This fact will be used to establish exact solution of the latter by the former in the following
principal theorem of the paper which also provides a method of solution as well.
Theorem 2.1 Existence of Exact Vertex Solution for Finite Value of Smoothing Parameter
R be bounded below on the polyhedral set S that contains no straight lines
going to infinity in both directions, let f be concave on R k , let h - 0 and let - be a fixed positive
number. Then for a sufficiently large positive but finite value ff 0 of ff, the smooth problem (7) has
a vertex solution that also solves the original nonsmooth problem (6).
Proof Note first that the smooth problem (7) is equivalent to the following concave minimization
problem
min
Since the objective function of this problem is concave in (s; z) on R 2k and is bounded below on T,
it follows by [23, Corollaries 32.3.3 and 32.3.4] that it has a vertex (s(ff); z(ff)) of T as a solution
for each ff ? 0. Since T has a finite number of vertices, one vertex, say (-s;
z), will repeatedly solve
problem Hence for ff i - ff 0 ,
where the last inequality follows from (8). Letting i \Gamma! 1 it follows that
z
s solves (6). Since (-s; -
z) is a vertex of T , it follows that -
s is a vertex of
This theorem immediately suggests an algorithmic approach for solving our problem (2) as
follows. We first rewrite (2) as the following equivalent problem
min
By making the identifications
x
y
problem (12) and hence problem (2) becomes a special case of problem (6) which we shall solve
in its smooth version (7). More specifically the smooth version of (2) is the following concave
minimization problem:
min
By solving this problem for a sufficiently large positive ff it follows by Theorem 2.1 that we have
solved our original problem (2). We turn our attention now to solving (14) by a finitely terminating
successive linearization algorithm.
3 The Concave Minimization Algorithm
The finite method that we shall propose is the successive linear approximation (SLA) method of
minimizing a concave function on a polyhedral set which is a finitely terminating stepless Frank-
Wolfe algorithm [9]. In [18] finite termination of the SLA was established for a differentiable concave
function, and in [20] for a nondifferentiable concave function using its supergradient. We state now
the SLA for problem (14) which has a differentiable concave objective function.
Algorithm 3.1 Successive Linearization Algorithm (SLA) Start with a random x 0 2 R n ,
Having
Stop when
By [18, Theorem 4.2] we have the following finite termination result for the SLA algorithm.
Theorem 3.2 SLA Finite Termination The SLA 3.1 generates a finite sequence f(x
with strictly decreasing objective function values for problem (14) and terminating at an - i satisfying
the minimum principle necessary optimality condition
4 Application and Numerical Testing
We wish to determine whether x-component suppression or x-norm reduction of an observed linear
system which is a corruption of a true system leads to an improved approximation
of the true system. One can relate this to a machine learning framework by treating the first system
as a training set, and the second system as a testing set [12]. The linear systems used are based
upon ideas related to signal processing [10, 28] and more specifically to an example in [1, Equation
(8)].
We consider the following true signal
We assume that the true signal g(t) cannot be sampled precisely, but that the following observed
signal can be sampled:
~
sampled at times : t
We further assume that we do not know the true signal g(t) (18), and we attempt to model it
as:
The problem now is to compute the coefficients x
so that we
can adequately recover g(t), given only the noisy data ~ g(t i ) (19). Notice that by substituting the
following coefficient vector x   into (20), -
Thus the true linear system (testing set) is then given by:
and is solved exactly by x   of (21).
The observed linear system (training set)
number with
We will refer to a solution of problem (14), with b of (14) replaced by b computed by the
Successive Linearization Algorithm (SLA 3.1) as a PLNA solution. Similarly, we shall refer to a
solution of problem (4), with b replaced by b as an LLNA solution. We note here that for all
experiments, the value of ff in the negative exponential of (14) is 5.0. Scalars are considered zero
if they are in the interval [\Gamma1e \Gamma 8; 1e \Gamma 8]. The components of the initial starting point x 0 for
SLA 3.1 were sampled from a normal distribution with mean = 0 and standard deviation = 1. The
components of the initial point were sampled then fixed for all runs as:
We now focus our attention on four approaches and compare solutions obtained by the PLNA
and LLNA methods with solutions obtained by least squares and by a combinatorial search.
4.1 Comparison of PLNA, LLNA and Least Squares
We compute solutions of the observed system are defined in (23),
by PLNA, LLNA and by least squares. These solutions are then evaluated by the observed system
(training set) residual kAx and the true system (testing set) residual kAx \Gamma bk 1 and
graphically comparing the recovered signal - g(t) (20) to the true signal g(t) (18).
The PLNA solution x(-) of for a given - is computed by solving by SLA 3.1 the
concave minimization problem (14) with b replaced by b
min
The LLNA solution x(-) of Ax = b+p, for a given - is computed by solving the linear program
(4) with b replaced by b
min
The least squares solution is a minimizer of kAx and is a solution to the normal
equations:
Although the 26 \Theta 10 matrix A defined by (23) has rank 10, the matrix A 0 A is numerically
singular with smallest eigenvalue less than 10 \Gamma14 . Thus we resort to a singular value decomposition
approach for solving (27).
We determine an approximate solution x(ls) to (27) by the following method which utilizes the
singular value decomposition [27]. Ordinary MATLAB [21] commands such as
our perturbed system give an x with an error compared to
given by the method described below, where x   is efined by (21) and the
perturbation vector p components are sampled from a normal distribution with mean = 0, standard
Algorithm 4.1 Least Squares via Singular Value Decomposition. Let A 2 R m\Thetan with
- be a small positive tolerance.
1. Determine the economy singular value decomposition of A [21, svd(A,0)], U 2 R m\Thetan
R n\Thetan
2. Determine the index r such that oe i - for
3. Set ~
m\Thetar to be the first r columns of U , ~
n\Thetar to be the first r columns of V and
~
r\Thetar to be diag(oe
4. Compute
which is a solution to:
min
For all runs - was fixed at 0.0001, which for our specific matrix A defined by (23), led to
in the above algorithm. That is we discarded the last 4 columns of U and V .
The PLNA problem (25) and the LLNA problem (26) were both solved for values of - 2
1:0g.

Figures

display results averaged over 5 noise
vectors elements sampled from a normal distribution with mean = 0, standard
deviation = 1. The average kpk
In

Figure

1 we plot averages of kAx(-) for the various values of -, measuring how
"well" the PLNA and LLNA solutions solve the corrupted observed linear system. Also plotted
is the average of kAx(ls) measuring how "well" the least squares solution (Algorithm
4.1) solves the observed system p. As can be proved, the PLNA and LLNA errors are a
non-decreasing functions of - and are worse than the corresponding least squares error. However
on the true system the results are reversed. See next paragraph.
In

Figure

2 we plot averages of kAx(-) \Gamma bk 1 for both PLNA and LLNA for various values of
-, measuring how "well" the PLNA solution (25) solves the true linear system. Also plotted is the
Suppression Parameter l
Observed
System
||Ax-b-p||Least Squares
PLNA
LLNA

Figure

1: Average versus -, where x(-) is a PLNA solution (25) in the curve
marked PLNA and is an LLNA solution of (26) for the curve marked LLNA, compared with average
is the least squares solution (27) by Algorithm 4.1. The results are
averaged over 5 noise vectors p. The PLNA and LLNA solutions were computed for values of
Suppression Parameter l
True
System
2.6, 10.7
2.8, 2.8
2.6, 5.3
2.6,
2.2, 4.4
2.4, 1.4
1.8, 4.0
2.2, 1.3
1.8, 4.0
2.0, 1.2
1.8, 3.9
1.6, 1.1
1.6, 3.9
1.0, 1.3
1.0, 0.4 1.00.4Least Squares
PLNA
LLNA

Figure

2: Average kAx(-) \Gamma bk 1 versus -, where x(-) is a PLNA solution (25) in the curve marked
PLNA and is an LLNA solution of (26) for the curve marked LLNA, compared with the average
is the least squares solution (27) solved by Algorithm 4.1. These results
are averaged over 5 noise vectors p. The PLNA and LLNA solutions were computed for values of
above/below the curves labelled "PLNA"
and "LLNA" at various values of - indicate the average number of nonzero elements in x(-) and
when followed by a second number, that number denotes kx(-)k 1 .
average of kAx(ls) \Gamma bk 1 , measuring how "well" the least squares solution (Algorithm 4.1) solves
In

Figure

3 we compare averages of 1-norm distances from the true solution x   (21) to the
PLNA and LLNA solutions x(-) and the averages of 1-norm distances from x   to the least squares
solution x(ls). Recall that the true solution x   is such that Ax  b. Note that for - 0:01, the
PLNA and LLNA distances are smaller than the least squares distance. For - 1, x(- 0 and
even though kx(-) \Gamma x   k 1 is small, this solution is poor from a signal recovery point of view since
the zero vector gives the worst discrepancy between the true signal and the recovered signal at 26
discrete points (see Figure 2).
In

Figure

4(a) we plot the true signal, the observed signal and the signal recovered by solving,
for one noise vector p, PLNA (25) with Figure 4(b) displays
the true signal, the observed signal and signal recovered for the same problem by least squares
solved by Algorithm 4.1. This is probably the most significant result. The signal recovered by
both PLNA and LLNA is considerably closer to the the true signal than that obtained by the least
squares solution.
4.2 Comparison of PLNA and LLNA with Combinatorial Search
In this section, we reformulate our PLNA problem so that the solution x(-) has a fixed number of
nonzero elements, for k 2
\Gammay
# of nonzero elements of
We also formulate the LLNA similarly as follows:
Similarly, for k 2 ng, the combinatorial search solution x c is obtained by solving:
of nonzero elements of
Notice that x c is determined by enumerating all subsets of size k of a set of n elements, or
subsets. This is a rather expensive procedure computationally requiring two orders of magnitude
more time than PLNA and LLNA.

Figure

5 displays results averaged over 5 noise vectors p 2 R m with elements sampled from
a normal distribution with mean = 0, standard deviation
20:1777). Plotted are averages of kAx(-) measuring how
"well" the PLNA, LLNA and combinatorial solutions solve the observed system. Also plotted are
averages of kAx(-) \Gamma bk 1 and kAx c \Gamma bk 1 for each k, measuring how "well" the solutions solve the
true system.

Figure

6 displays the average 1-norm distance between x   of (21) and the solutions obtained by
PLNA, LLNA and combinatorial search. The averages are over 5 noise vectors p.

Figure

7(a), which for convenience duplicates Figure 4(a), displays the true signal, the observed
signal and the signal recovered by solving PLNA (25) for the value of and the signal
Suppression Parameter l
Distance
to
True
Solution
||x-x

||Least Squares
PLNA
LLNA

Figure

3: Average kx(-) \Gamma x   k 1 versus -, where x(-) is a PLNA solution (25) in the curve marked
PLNA and is an LLNA solution of (26) for the curve marked LLNA, compared with the average
is the least squares solution (27) solved by Algorithm 4.1. The true
solution x   (21) is such that Ax  b. The PLNA and LLNA solutions were computed for values
of
012Observed
Actual
PLNA
LLNA
(a) Dashed curves are the recovered signal -
g(t) with
coefficient vector x(-) determined by (25) with
0:3 and kAx(-) \Gamma and by (26)
with
Observed
Actual
Least Squares
(b) Dashed curve is the recovered signal - g(t) with
coefficient vector x(ls) determined by least squares
solution (27) solved by Algorithm 4.1. Note:

Figure

4: Signal Recovery. Solid curve is the true signal g(t). Circles are the observed signal
sampled at discrete times and the dashed curves are the recovered signals.
Number of Nonzeros k in Solution x
Average
Observed
True
Figure

5: Comparison of PLNA (30) and LLNA (31) with combinatorial search (32). Average
is '2' for PLNA and 4 for LLNA. Average kAx c \Gamma bk 1 is '+' for combinatorial
solution x c .
Number of Nonzeros k in Solution x
Average
Distance
to
True
||x-x

Figure

Comparison of PLNA (30) and LLNA (31) with combinatorial search (32). Average
is '2' for PLNA and 4 for LLNA. The true solution x   is
such that Ax
Observed
Actual
PLNA
LLNA
(a) Dashed curves are the recovered signal -
g(t) with
coefficient vector x(-) determined by (25) with
0:3 and kAx(-) \Gamma and by
LLNA.
Combinatorial
Observed
Actual
(b) Dashed curve is the recovered signal - g(t) with
coefficient vector xc determined by combinatorial
search with

Figure

7: Signal Recovery. Solid curve is the true signal g(t). Circles are the observed signal
sampled at discrete times and the dashed curves are the recovered signals.
recovered by LLNA (26) for 0:8. Figure 7(b) displays the true signal, the observed signal and
signal recovered by combinatorial search solution x c of (32) for 2.
4.3 Observations
We make the following observations with respect to the comparison between the PLNA, LLNA
solutions and least squares solutions.
1. For all values of - 0:05 tested, the average observed system (training set) residual kAx(ls) \Gamma
strictly less than the average kAx(-) LLNA. The least
squares Algorithm 4.1 for solving (27) produced "better" solutions to the observed system
Figure 1. However:
2. For values of - 2 [0:01; 0:90] tested, the PLNA average true system (testing set) residual
strictly less than the average kAx(ls) \Gamma bk 1 indicating that PLNA produced
"better" solutions to the true system in comparison with least squares. For values of
tested, the average true system residual with solutions determined by LLNA
was also strictly less than the corresponding least squares true system residuals. See Figure
2. PLNA with and an average of 2.2 nonzero terms achieved an error reduction
of 38.85% over the corresponding error obtained by the least squares solution. LLNA with
produced an average 1-norm true system residual that was 52.98% less than the least
squares residual.
3. For values of - ? 0:1 tested, the average determined by both PLNA and LLNA,
was 2 orders of magnitude less than the average kx(ls) \Gamma x   k. Hence the PLNA and LLNA
solutions were "closer" to recovering the true signal g(t) (18). See Figure 3.
4.

Figure

4, shows the most significant comparison between PLNA, LLNA and least squares:
A much more accurate recovery of the true signal by both PLNA and LLNA than by least
squares.
We note the following with respect to the comparison between the PLNA, LLNA solutions and
the solutions obtained by combinatorial search.
1. For 7, the average PLNA kAx(-) \Gamma bk 1 was strictly less than the average kAx c \Gamma
the average PLNA kAx(-) \Gamma bk 1 was less than or equal to 1.634 times
the average kAx c \Gamma bk 1 . For 7, the average LLNA kAx(-) \Gamma bk 1 was strictly
less than the corresponding average true system residual with the combinatorial solutions.
For 4, the average LLNA kAx(-) \Gamma bk 1 was less than or equal to 1.114 times the
corresponding average kAx c \Gamma bk. See Figure 5.
2. For k - 3, the average kx(-) \Gamma x   k 1 , for both PLNA and LLNA, was strictly less than the
average by orders of magnitude. For
than or equal to average kx c \Gamma x   k 1 . See Figure 6.
3. The minimum over of the true system 1-norm residual of 5.3867 occurs for
with the solution obtained by combinatorial search. The true system residual for PLNA
with and the true system residual for LLNA is 6:0022. We note that when
computing the PLNA and LLNA solutions for 2, the first value of - found (by a bisection
search) such that the solution has 2 nonzero elements was chosen. This fact accounts for the
discrepancy between the true system residuals in Figure 5 and Figure 2.
4.

Figure

7 shows recovery of the true signal by both PLNA and LLNA which is as good or even
better than the recovered signal by a lengthy combinatorial search.
The time needed by each approach to compute a solution was determined by performing a
single run on a Sun SparcStation 20 with 96 megabytes of memory running MATLAB 5.1, using
the commands "tic" and "toc" [21]. All linear programs were solved with CPLEX [7] interfaced
with MATLAB. Solving the PLNA problem with
seconds. Solving the LLNA problem with seconds. Determining the
least squares solution by Algorithm 4.1 with seconds. Determining the
solution by combinatorial search with seconds.
Solutions computed by PLNA and LLNA were at most superior or at least comparable to those
obtained by combinatorial search (32), yet needing two orders of magnitude less time to compute.
5 Conclusion
A theoretically justifiable fast finite algorithm has been proposed for solving linear systems corrupted
by noise or errors in measurement. The parsimonious approach (PLNA) attempts to set
to zero as many components of the solution vector as possible while minimizing the residual error
of the corrupted system, whereas the least norm approach (LLNA) minimizes the norm of the
solution as well as the residual. Numerical evidence indicates that both these two approaches lead
to solutions with many zero components, and that such solutions may be closer by orders of magnitude
to the solution of the underlying uncorrupted system than other solutions of the corrupted
system obtained by either least squares or even by a time-consuming combinatorial search for a
solution with a minimal number of nonzero components. It is interesting to note that parametricly
minimizing the norm of the solution leads also to suppression of its components, and conversely
parametrically suppressing components of the solution also leads to a solution with a reduced norm.
Most importantly, PLNA and LLNA recover a much more accurate signal than that obtained by
least squares and much faster than that obtained by a lengthy combinatorial search.

Acknowledgement

We are indebted to the referees for constructive comments that led to considerable improvements.
In particular we are indebted to a referee who suggested the inclusion of the LLNA approach in
our comparative tests.



--R

The constrained total least squares technique and its application to harmonic superposition.
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems.
A support vector machine approach to decision trees.
Occam's razor.
Clustering via concave minimization.
Feature selection via mathematical programming.
CPLEX Optimization Inc.
Theory of Vector Optimization.
An algorithm for quadratic programming.
Least Square Estimation With Applications to Digital Signal Processing.
An analysis of the total least squares problem.
Fundamentals of Artificial Neural Networks.
Formulation and solution of structured total least norm problems for parameter estimation.
The Total Least Squares Problem
Solving Least Squares Problems.
Optimal brain damage.
Misclassification minimization.
Machine learning via polyhedral concave minimization.
Mathematical programming in data mining.
Solution of general linear complementarity problems via nondifferentiable concave minimization.
The MathWorks
Introduction to Optimization.
Convex Analysis.
Total least norm formulation and solution for structured problems.
Overfitting avoidance as bias.
Readings in Machine Learning.
Introduction to Linear Algebra.
Discrete Random Signals and Statistical Signal Processing.
The Nature of Statistical Learning Theory.
The Mathematics of Generalization
--TR

--CTR
Jinbo Bi , Kristin Bennett , Mark Embrechts , Curt Breneman , Minghu Song, Dimensionality reduction via sparse support vector machines, The Journal of Machine Learning Research, 3, 3/1/2003
Glenn Fung , Olvi L. Mangasarian, Data selection for support vector machine classifiers, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.64-70, August 20-23, 2000, Boston, Massachusetts, United States
Glenn Fung, The disputed federalist papers: SVM feature selection via concave minimization, Proceedings of the conference on Diversity in computing, p.42-46, October 15-18, 2003, Atlanta, Georgia, USA
Glenn M. Fung , Olvi L. Mangasarian , Alexander J. Smola, Minimal kernel classifiers, The Journal of Machine Learning Research, 3, p.303-321, 3/1/2003
Gunnar Rtsch , Ayhan Demiriz , Kristin P. Bennett, Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces, Machine Learning, v.48 n.1-3, p.189-218, 2002
P. S. Bradley , O. L. Mangasarian , D. R. Musicant, Optimization methods in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Gunnar Rtsch , Sebastian Mika , Bernhard Schlkopf , Klaus-Robert Mller, Constructing Boosting Algorithms from SVMs: An Application to One-Class Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1184-1199, September 2002
minimal cardinality;least norm approximation